Proof that A graph G is bipartite if and only if G does not contain an odd cycle .

Published On :2023-08-09 20:57:43

 Theorem: A graph G is bipartite if and only if G does not contain an odd cycle.

Proof: Suppose G is bipartite.

Since odd cycles are not bipartite graphs, then G can’t contain an odd cycle.

→ Suppose G is a graph that does not contain an odd cycle.

Let v be a vertex of G.

Color the vertex v white.

Let u be any other vertex of G.

If the distance between u & v is odd, then color u black.

Whereas if the distance between u & v is even then color u white.

Suppose u₁ & u₂ are two vertices whose color is white.

Then the distance between v & u₁ is even and the distance between v & u₂ is also even.

If u₁ & u₂ are adjacent, then the cycle formed by the union of the path 

between v & u₁, the path between v & u₂ and the edge u₁ u₂ is an odd cycle.

This is a  contradiction since G has no odd cycle.

Thus the vertices whose color is white are not adjacent.

Similarly, we get any vertices whose color is black are not adjacent. So G is Bipartite.

Corollary: Trees are bipartite.