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 V1 and V2 such that any edge in E must have exactly one endpoint in each of V1 and V2.

That is, G does not have any edges whose endpoints are both in V1, or both in V2.

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 Km,n, is the bipartite graph G=(V1βˆͺV2,E) where |V1|=m, |V2|=n, V1∩V2=βˆ…, and

E={(u,v):u∈V1,v∈V2}.

That is, there is an edge in between any vertex in V1 and any vertex in V2.

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.