# Bipartite graph

A simple bipartite graph

## Definition

An undirected graph $G=(V,E)$ is called bipartite if there is a partition of $V$, $V=V_{1} \dot\cup V_{2}$, such that for every edge $\{ v,w \} \in E$ it is $v \in V_{1} \Leftrightarrow w \in V_{2}$.

## Absence of odd cycles

Theorem: An undirected graph $G=(V,E)$ is bipartite if, and only if, $G$ has no cycle of odd length.

Proof:

• First suppose $G$ contains at least one cycle $v_{1} - v_{2} - ... - v_{k} - v_{1}$ of odd length $k \in \N$. Without loss of generality, we assume $v_{1} \in V_{1}$. Then it is $v_{i} \in V_{1}$ for all odd $i$ and $v_{i} \in V_{2}$ for all even $i$. The edge $\{ v,w \}$ contradicts bipartiteness.
• Now suppose that $G$ contains no cycle of odd length. We will prove bipartiteness constructively. Without loss of generality, we may assume that $G$ is connected (otherwise, each connected component may be considered separately). We choose an node $v\in V$, which will be fix, and start with an arbitrary node $u \in V$ and label each node "$x$" if its distance (smallest number of edges) from $v$ is even, and "$y$" otherwise. Suppose for a contradiction that there is an edge $\{ v,w \}$ such that both endnotes have the same label. Then the shortest paths from $u$ to $v$ and $w$ plus this edge from an odd cycle (which is not simple but can be easily reduced to a simple cycle, which is odd again).