Graph is Bipartite iff No Odd Cycles
Theorem
Let $G$ be an undirected graph.
Then $G$ is bipartite if and only if it has no odd cycles.
Proof
Sufficient Condition
Let $G = \struct {V, E}$ be bipartite.
So, let $V = A \cup B$ such that $A \cap B = \O$ and that all edges $e \in E$ are such that $e$ is of the form $\set {a, b}$ where $a \in A$ and $b \in B$.
(This is the definition of a bipartite graph.)
Suppose $G$ has (at least) one odd cycle $C$.
Let the length of $C$ be $n$.
Let $C = \tuple {v_1, v_2, \ldots, v_n, v_1}$.
Without loss of generality, let $v_1 \in A$. It follows that $v_2 \in B$ and hence $v_3 \in A$, and so on.
Hence we see that $\forall k \in \set {1, 2, \ldots, n}$, we have:
- $v_k \in \begin{cases}
A : & k \text{ odd} \\ B : & k \text{ even} \end{cases}$
But as $n$ is odd, $v_n \in A$.
But $v_1 \in A$, and $v_n v_1 \in C_n$.
So $v_n v_1 \in E$ which contradicts the assumption that $G$ is bipartite.
Hence if $G$ is bipartite, it has no odd cycles.
$\Box$
Necessary Condition
It is enough to consider $G$ as being connected, as otherwise we could consider each component separately.
Suppose $G$ has no odd cycles.
Choose any vertex $v \in G$.
Divide $G$ into two sets of vertices like this:
- Let $A$ be the set of vertices such that the shortest path from each element of $A$ to $v$ is of odd length
- Let $B$ be the set of vertices such that the shortest path from each element of $B$ to $v$ is of even length.
Then $v \in B$ and $A \cap B = \O$.
Suppose $a_1, a_2 \in A$ are adjacent.
Then there would be a closed walk of odd length $\tuple {v, \ldots, a_1, a_2, \ldots, v}$.
But from Graph containing Closed Walk of Odd Length also contains Odd Cycle, it follows that $G$ would then contain an odd cycle.
This contradicts our initial supposition that $G$ contains no odd cycles.
So no two vertices in $A$ can be adjacent.
By the same argument, neither can any two vertices in $B$ be adjacent.
Thus $A$ and $B$ satisfy the conditions for $G = \struct {A \cup B, E}$ to be bipartite.
$\blacksquare$