SKEDSOFT

Bipartite Graphs: Sometimes a graph has the property that its vertex set can be divided into two disjoint subsets such that each edge connects a vertex in one of these subsets to a vertex in the other subset. For example, consider the graph representing marriages between men and women in a village, where each person is represented by a vertex and a marriage is represented by an edge. In this graph, each edge connects a vertex in the subset of vertices representing males and a vertex in the subset of vertices representing females. This leads us to Definition 5.

DEFINITION 6 A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2 (so that no edge in G connects either two vertices in V1 or two vertices in V2). When this condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G. In Example1 we will show that C6 is bipartite, and in Example 10 we will show that K3 is not bipartite.

EXAMPLE 1 C6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a vertex in V2.

EXAMPLE 2 K3 is not bipartite. To verify this, note that if we divide the vertex set of K3 into two disjoint sets, one of the two sets must contain two vertices. If the graph were bipartite, these two vertices could not be connected by an edge, but in K3 each vertex is connected to every other vertex by an edge.

EXAMPLE 3 Are the graphs G and H displayed in Figure 8 bipartite?

Solution: Graph G is bipartite because its vertex set is the union of two disjoint sets, {a, b, d} and {c, e, f, g}, and each edge connects a vertex in one of these subsets to a vertex in the other subset. (Note that forGto be bipartite it is not necessary that every vertex in {a, b, d} be adjacent to every vertex in {c, e, f, g}. For instance, b and g are not adjacent.) Graph H is not bipartite because its vertex set cannot be partitioned into two subsets so that edges do not connect two vertices from the same subset. (The reader should verify this by considering the vertices a, b, and f .) Theorem 4 provides a useful criterion for determining whether a graph is bipartite.

THEOREM 4 A simple graph is bipartite if and only if it is possible to assign one of two different colors to each vertex of the graph so that no two adjacent vertices are assigned the same color.
Proof: First, suppose thatG = (V ,E) is a bipartite simple graph. Then V = V1 ∪ V2, where V1 and V2 are disjoint sets and every edge in E connects a vertex in V1 and a vertex in V2. If we assign one color to each vertex in V1 and a second color to each vertex in V2, then no two adjacent vertices are assigned the same color.
Now suppose that it is possible to assign colors to the vertices of the graph using just two colors so that no two adjacent vertices are assigned the same color. Let V1 be the set of vertices assigned one color and V2 be the set of vertices assigned the other color. Then, V1 and V2 are disjoint and V = V1 ∪ V2. Furthermore, every edge connects a vertex in V1 and a vertex in V2 because no two adjacent vertices are either both in V1 or both in V2. Consequently, G
is bipartite. We illustrate how Theorem 4 can be used to determine whether a graph is bipartite in Example 4.

EXAMPLE 12 Use Theorem 4 to determine whether the graphs in Example 11 are bipartite.
Solution: We first consider the graph G. We will try to assign one of two colors, say red and blue, to each vertex in G so that no edge in G connects a red vertex and a blue vertex.Without loss of generality we begin by arbitrarily assigning red to a. Then, we must assign blue to c, e, f , and g, because each of these vertices is adjacent to a. To avoid having an edge with two blue endpoints, we must assign red to all the vertices adjacent to either c, e, f , or g. This means that we must assign red to both b and d (and means that a must be assigned red, which it already has been).We have now assigned colors to all vertices, with a, b, and d red and c, e, f , and g blue. Checking all edges, we see that every edge connects a red vertex and a blue vertex. Hence, by Theorem 4 the graph G is bipartite. Next, we will try to assign either red or blue to each vertex in H so that no edge in H connects a red vertex and a blue vertex.Without loss of generality we arbitrarily assign red to a. Then, we must assign blue to b, e, and f , because each is adjacent to a. But this is not possible because e and f are adjacent, so both cannot be assigned blue. This argument shows that we cannot assign one of two colors to each of the vertices of H so that no adjacent vertices are assigned the same color. It follows by Theorem 4 that H is not bipartite.

EXAMPLE 13 Complete Bipartite Graphs A complete bipartite graph Km,n is a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. The complete bipartite graphs K2,3, K3,3, K3,5, and K2,6 are displayed in Figure 9.