Bipartite graph

From Algowiki
Jump to: navigation, search
A simple bipartite graph

Definition

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

Absence of odd cycles

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

Proof:

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