We have already seen how bipartite graphs arise naturally in some circumstances. Here we explore bipartite graphs a bit more.
It is easy to see that all closed walks in a bipartite graph must have even length, since the vertices along the walk must alternate between the two parts. Remarkably, the converse is true. We need one new definition:
Definition 5.4.1 The distance between vertices $v$ and $w$, $\d(v,w)$, is the length of a shortest walk between the two. If there is no walk between $v$ and $w$, the distance is undefined. $\square$
Theorem 5.4.2 $G$ is bipartite if and only if all closed walks in $G$ are of even length.
Proof. The forward direction is easy, as discussed above.
Now suppose that all closed walks have even length. We may assume that $G$ is connected; if not, we deal with each connected component separately.
Let $v$ be a vertex of $G$, let $X$ be the set of all vertices at even distance from $v$, and $Y$ be the set of vertices at odd distance from $v$. We claim that all edges of $G$ join a vertex of $X$ to a vertex of $Y$. Suppose not; then there are adjacent vertices $u$ and $w$ such that $\d(v,u)$ and $\d(v,w)$ have the same parity. Then there is a closed walk from $v$ to $u$ to $w$ to $v$ of length $\d(v,u)+1+\d(v,w)$, which is odd, a contradiction. $\qed$
The closed walk that provides the contradiction is not necessarily a cycle, but this can be remedied, providing a slightly different version of the theorem.
Proof. Again the forward direction is easy, and again we assume $G$ is connected. As before, let $v$ be a vertex of $G$, let $X$ be the set of all vertices at even distance from $v$, and $Y$ be the set of vertices at odd distance from $v$. If two vertices in $X$ are adjacent, or two vertices in $Y$ are adjacent, then as in the previous proof, there is a closed walk of odd length.
To finish the proof, it suffices to show that if there is a closed walk $W$ of odd length then there is a cycle of odd length. The proof is by induction on the length of the closed walk.
If $W$ has no repeated vertices, we are done. Otherwise, suppose the closed walk is $$v=v_1,e_1,\ldots,v_i=v,\ldots,v_k=v=v_1.$$ Then $$ v=v_1,\ldots,v_i=v \quad\hbox{and}\quad v=v_i,e_i,v_{i+1},\ldots, v_k=v $$ are closed walks, both are shorter than the original closed walk, and one of them has odd length. By the induction hypothesis, there is a cycle of odd length. $\qed$
It is frequently fruitful to consider graph properties in the limited context of bipartite graphs (or other special types of graph). For example, what can we say about Hamilton cycles in simple bipartite graphs? Suppose the partition of the vertices of the bipartite graph is $X$ and $Y$. Because any cycle alternates between vertices of the two parts of the bipartite graph, if there is a Hamilton cycle then $|X|=|Y|\ge2$. In such a case, the degree of every vertex is at most $n/2$, where $n$ is the number of vertices, namely $n=|X|+|Y|$. Thus the Ore condition ($\d(v)+\d(w)\ge n$ when $v$ and $w$ are not adjacent) is equivalent to $\d(v)=n/2$ for all $v$. This means the only simple bipartite graph that satisfies the Ore condition is the complete bipartite graph $K_{n/2,n/2}$, in which the two parts have size $n/2$ and every vertex of $X$ is adjacent to every vertex of $Y$. The upshot is that the Ore property gives no interesting information about bipartite graphs.
Of course, as with more general graphs, there are bipartite graphs with few edges and a Hamilton cycle: any even length cycle is an example.
We note that, in general, a complete bipartite graph $K_{m,n}$ is a bipartite graph with $|X|=m$, $|Y|=n$, and every vertex of $X$ is adjacent to every vertex of $Y$. The only such graphs with Hamilton cycles are those in which $m=n$.
Exercises 5.4
Ex 5.4.1 Prove that there is a bipartite multigraph with degree sequence $d_1,\ldots,d_n$ if and only if there is a partition $\{I,J\}$ of $[n]$ such that $$\sum_{i\in I}d_i=\sum_{i\in J} d_i.$$
Ex 5.4.2 What is the smallest number of edges that can be removed from $K_5$ to create a bipartite graph?
Ex 5.4.3 A regular graph is one in which the degree of every vertex is the same. Show that if $G$ is a regular bipartite graph, and the common degree of the vertices is at least 1, then the two parts are the same size.
Ex 5.4.4 A perfect matching is one in which all vertices of the graph are incident with exactly one edge in the matching. Show that a regular bipartite graph with common degree at least 1 has a perfect matching. (We discussed matchings in section 4.5.)