Proof a graph is bipartite if and only if it contains no odd cycles

Solution 1:

One direction is very easy: if $G$ is bipartite with vertex sets $V_1$ and $V_2$, every step along a walk takes you either from $V_1$ to $V_2$ or from $V_2$ to $V_1$. To end up where you started, therefore, you must take an even number of steps.

Conversely, suppose that every cycle of $G$ is even. Let $v_0$ be any vertex. For each vertex $v$ in the same component $C_0$ as $v_0$ let $d(v)$ be the length of the shortest path from $v_0$ to $v$. Color red every vertex in $C_0$ whose distance from $v_0$ is even, and color the other vertices of $C_0$ blue. Do the same for each component of $G$. Check that if $G$ had any edge between two red vertices or between two blue vertices, it would have an odd cycle. Thus, $G$ is bipartite, the red vertices and the blue vertices being the two parts.

Solution 2:

does this theorem have a common name?

It is sometimes called König's Theorem (1936), for example in lecture notes here.

However, this name is ambiguous.

Solution 3:

The following is an expanded version of Brian's answer. Brian's answer is almost perfect, except that there may be a gap between "if G had any edge between two red vertices or between two blue vertices" and "it would have an odd cycle", which is not that obvious, at least to me(since we can only conclude that there exists a closed walk of odd numbers of edges). We first prove a lemma stating that if there is an odd closed walk in a graph, then there is an odd closed cycle.

Lemma 1 If there is an odd closed walk in a graph, then there is an odd closed cycle.

Proof$\;$ We induct on the number of edges $k$ of the odd closed walk. The base case $k=1$, when the closed walk is a loop, holds trivially. Assume that, for some positive integer $r > 1$, Lemma 1 is true for all odd numbers $k\le2r-1$. Let $W=(w_1, \dots, w_{2r+1}, w_1)$ be a closed walk of $2r+1$ edges. If all vertices in $W$ is different except for $w_1$, then we have a cycle of length $2r+1$. If there exists two identical vertices $w_i=w_j$ for $1<i<j\le 2r+1$, then $W$ can be written as $(w_1, \dots,w_i, \dots, w_j,\dots, w_1)$. Thus, we now have two closed walks $W_1=(w_i,w_{i+1} \dots, w_j)$ and $W_2=(w_j,w_{j+1} \dots, w_i)$. The summation of the length of $W_1$ and $W_2$ equals to the length of $W$. Since $W$ is of odd length, one of $W_1$ and $W_2$ must be of odd length $\le 2r-1$. By our assumption, there must be a an odd cycle in $W_1$ or $W_2$, and thus in $W$, which completes our induction. $\square$

Theorem 1 If there are no odd cycles in a graph, then the graph is bipartite.

Proof$\;$ Suppose there is no odd cycles in graph $G=(V,E)$. It is also assumed that, without loss of generality, $G$ is connected. Then $V$ can be partitioned into $(A,B)$, where $$A=\{v\in V|\text{the shortest path between $v$ and $v_0$ is of even length}\}$$ $$B=\{v\in V|\text{the shortest path between $v$ and $v_0$ is of odd length}\}$$ Next we prove that there is no edge between any two vertices in $A$ or $B$. Suppose for contradiction that there exists an edge $(x,y)\in E$ such that $x,y \in A$ or $x,y \in B$ . Then the shortest path from $x$ to $v_0$, the shortest path from $y$ to $v_0$, together with edge $(x,y)$, form a closed walk: $(v_0, \dots,x,y, \dots,v_0)$, which is of odd length. By lemma 1, $G$ contains an odd cycle, which is a contradiction.

Therefore, $G$ is a bipartite graph between $A$ and $B$. $\square$