Show that Every Bipartite Graph is Perfect

In this article, we will show that every bipartite graph is perfect.

Suppose a Bipartite Graph G(V, E). Let V1 and V2 be the sets such that every edge in G connects a vertex in V1 and a vertex in V2. Graph G is a perfect graph if, for every subgraph S, the clique number of S is equal to the chromatic number of S.

Chromatic number is denoted by $\chi(G)$ and Clique number is denoted by $\omega(G)$ .

Condition for Perfect Graph

$\chi(S) = \omega(S)\; for\; all\; sub-graph\; S\; of\; G$

We shall prove that the above condition is true for every sub-graph S of Bipartite Graph G.

Proof that every bipartite graph is perfect

Case 1 ( Number of Vertices in S = 1 )

Every sub-graph with only 1 vertex has $\chi(G) = 1$ and $\omega(S) = 1$ .

Case 2 ( Number of Vertices in S = 2 )

Suppose the 2 vertices do not have an edge between them. In that case, $\chi(G) = 1$ and $\omega(S) = 1$ .

Suppose the 2 vertices are connect by an edge. Then $\chi(G) = 2$ and $\omega(S) = 2$ .

Case 3 ( Number of Vertices in S > 2 )

Suppose all vertices are disconnects. Therefore $\chi(G) = 1$ and $\omega(S) = 1$ .

Suppose some of the vertices are connected, therefore $\chi(G) = 2$ . As the original graph is bipartite, no edge can connect vertices belonging to the same set. This means we can never have a complete sub-graph of S of more than 2 vertices. Suppose a complete sub-graph $S'$ of size 3. It is impossible to divide vertices of $S'$ into V1 and V2 such that no edge connects vertices belonging to the same set. One of the sets will have more than 1 vertex which will violate the condition for Bipartite Graph. Thus, the clique of the sub-graph S $\omega(S) = 2$ .

Hence, we conclude that for every sub-graph S of a Bipartite Graph G, $\chi(S) = \omega(S)$ . Thus, every bipartite graph is a perfect graph.

Hence Proved.

References

Clique Number
Bipartite Graph Characteristics

Proof that every bipartite graph is perfect

Leave a Comment Cancel Reply