Bipartite Graph has No Odd Cycles
Contents |
Theorem
Let $G$ be an undirected graph.
Then $G$ is bipartite iff it has no odd cycles.
Proof
Sufficient Condition
Let $G = \left({V, E}\right)$ be bipartite.
So, let $V = A \cup B$ such that $A \cap B = \varnothing$ and that all edges $e \in E$ are such that $e$ is of the form $\left\{{a, b}\right\}$ 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 = \left({v_1, v_2, \ldots, v_n, v_1}\right)$.
WLOG, 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 \left\{{1, 2, \ldots, n}\right\}$, 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.
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 = \varnothing$.
Suppose $a_1, a_2 \in A$ are adjacent.
Then there would be a closed walk of odd length $\left({v, \ldots, a_1, a_2, \ldots, v}\right)$.
But from Closed Walk of Odd Length contains an 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 = \left({A \cup B, E}\right)$ to be bipartite.
$\blacksquare$
