Skip to main content

Section 5.6 Bipartite Graphs

Definition 5.6.1. Bipartite Graph.

A simple graph \(G = (V,E)\) is said to be bipartite if we can partition \(V\) into two disjoint sets \(V_1\) and \(V_2\) such that any edge in \(E\) must have exactly one endpoint in each of \(V_1\) and \(V_2\text{.}\)

That is, \(G\) does not have any edges whose endpoints are both in \(V_1\text{,}\) or both in \(V_2\text{.}\)

Consider the path \(P_6\) on six vertices.

It is bipartite, because we can partition \(V\) into two sets \(V_1 = \{1,3,5\}\) and \(V_2 = \{2,4,6\}\text{,}\) such that any edge in the graph has one endpoint in each of the partitions.

Which of the following graphs are bipartite? For those that are, give the bipartition, and redraw them to show the bipartition explicitly. For those that are not, explain why a bipartition cannot exist.

Explain how Checkpoint 5.1.3 relates to determining whether a certain graph is bipartite. Then answer the exercise.

As with trees, there is a nice characterization of bipartite graphs.

The proof of the ‘only if’ direction is left as an exercise; the ‘if’ direction will not be proven here.

Prove the ‘only if’ direction of Theorem 5.6.5 by contradiction. That is, assume that \(G\) has an odd cycle, then show that it cannot be bipartite.

Definition 5.6.8. Complete Bipartite Graph.

The complete bipartite graph on \(m\) and \(n\) vertices, denoted by \(K_{m,n}\text{,}\) is the bipartite graph \(G = (V_1 \cup V_2, E)\) where \(|V_1| = m\text{,}\) \(|V_2| = n\text{,}\) \(V_1 \cap V_2 = \varnothing\text{,}\) and

\begin{equation*} E = \{(u,v) : u \in V_1, v \in V_2\}\text{.} \end{equation*}

That is, there is an edge in between any vertex in \(V_1\) and any vertex in \(V_2\text{.}\)

The graph of \(K_{2,4}\text{:}\)

Draw the graphs of \(K_{1,2}\text{,}\) \(K_{4,1}\text{,}\) \(K_{3,3}\text{,}\) and \(K_{5,5}\text{.}\)

Find all pairs of natural numbers \((m,n)\) for which \(K_{m,n}\) is a tree.