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

Leave a Comment

Your email address will not be published. Required fields are marked *