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 u1 & u2 are two vertices whose color is white.
Then the distance between v & u1 is even and the distance between v & u2 is also even.
If u1 & u2 are adjacent , then the cycle formed by the union of the path between v & u1 , the path
between v & u2 and the edge u1 u2 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 .