3.5b Bipartite Graphs

Bipartite Graphs

A bipartite graph is a graph whose vertex set $V=U\cup W$ can be divided into two disjoint subsets $U$ and $W$, such that every edge connects a vertex in $U$ to a vertex in $W$, and vice-versa. That is, no edge connects two vertices within the same subset, so that $E\subseteq U\times W$. As such, a graph can only be bipartite if it contains no cycles of odd length.

Complete bipartite graphs are denoted as $K_{|U|,|W|}$.

Intuition

Although we can’t prove bipartition, we can think about as to why the sets $V$ and $E$ can be expressed using the two bipartite sets $L$ and $R$:

• The first fact is simply a union of the two groups of nodes, $L$ and $R$.
• The second fact states that $E$ is equal to or a subset of all possible combinations of edges between the two groups. **A graph where $E=L\times R$ (every vertex from one group connects to all of the vertices from the other) be expressed as $K_{|L|,|R|}$.

Example

Three Wells, Three Houses