# Bipartite graphs

The topic of this post is bipartite graphs. These are graphs whose vertex set can be partitioned into two parts, called partite sets, such that all edges $xy$ of the graph are such that $x$ and $y$ are in different partite sets. The most common examples of bipartite graphs are the trees and even cycles. Any union of bipartite graphs obviously yields another bipartite graph. The complete bipartite graph $K_{m,n}$ consists of two partite sets $X$ and $Y$ containing $m$ and $n$ elements respectively with all possible edges between $X$ and $Y$ filled out.

To conclude here is a list of characterizations.

Suppose $G$ is a graph with at least two vertices. The following are equivalent:

1. $G$ is bipartite.

2. Every cycle of $G$ is even.

3. $\chi(G)=2$.

Proof: $1 \Leftrightarrow 2$: Suppose $G$ is bipartite and there is a cycle $v_1v_2\cdots v_kv_1$ which has an odd number of edges. Now $v_i$ for odd $i$ is in the same partite set as $v_1$. But since the cycle is odd $v_1$ and $v_k$ are in the same partite set which is a contradiction.

Conversely suppose $G$ has no odd cycles and $x\in V(G)$. Let $X=\{y\in V(G):d(x,y)$ is even $\}$ and $Y=\{y\in V(G):d(x,y)$ is odd $\}$. Then $X$ and $Y$ partition $V(G)$. Suppose $pq\in E(G)$ and $p,q\in X$. Neither $p$ nor $q$ is $x$ for otherwise $d(x,q)$ (resp $d(x,p)$) is odd. So it makes sense to talk of a path from $x$ to $p$ (resp $q$). Let $x=v_0v_1\cdots v_{2k-1}v_{2k}=p$ and $x=w_0w_1\cdots w_{2m-1}w_{2m}=q$ be the shortest such paths. (Note that they are necessarily even). Let the last common vertex in the two paths be $v_i=w_i$. Now the cycle $v_iv_{i+1}\cdots v_{2k}w_{2m}w_{2m-1}\cdots w_{i+1}w_i=v_i$ is an odd cycle. This contradiction proves there are no edges within vertices of $X$. Similarly there are no edges within vertices of $Y$. The result follows. $1 \Leftrightarrow 3$: This is more of a restatement of the definition of a bipartite graph then a characterization, since the two partite sets may be considered as differently colored subsets of $V(G)$. $\Box$

In addition to the above general characterizations the following are also true:

a) G is bipartite iff the spectrum of $G$ is symmetric with respect to the origin.

b) Suppose $G$ is connected and $\lambda$ is its maximum eigenvalue. Then $G$ is bipartite iff $-\lambda$ is an eigenvalue of $G$.

c) Suppose $G$ is planar. Then $G$ is bipartite iff $b(R)$, the bound degree of a region $R$, is even for every region $R$.

I will defer a proof of these statements.