Odd-cycle characterization of bipartite graphs
= Odd-cycle characterization of bipartite graphs
A graph is <bipartite> if and only if it contains no <odd cycle>. One direction follows because every cycle alternates between the two vertex classes. For the converse, in each <connected component of a graph> choose a root and partition the vertices according to the parity of their <graph distance> from it. An edge joining equal parities would close an odd cycle, so every edge crosses the partition.