Page 677 - Discrete Mathematics and Its Applications

656 10 / Graphs

110 111
10 11 100 101

010 011
0 1
00 01 000 001
Q 1 Q 2 Q 3

FIGURE 6 The n-cube Q n ,n = 1, 2, 3.

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 V 1 and V 2 such that every edge in the graph connects a vertex in V 1 and a vertex in V 2
(so that no edge in G connects either two vertices in V 1 or two vertices in V 2 ). When this
condition holds, we call the pair (V 1 ,V 2 ) a bipartition of the vertex set V of G.

In Example 9 we will show that C 6 is bipartite, and in Example 10 we will show that K 3 is
not bipartite.

EXAMPLE 9 C 6 is bipartite, as shown in Figure 7, because its vertex set can be partitioned into the two sets
V 1 ={v 1 , v 3 , v 5 } and V 2 ={v 2 , v 4 , v 6 }, and every edge of C 6 connects a vertex in V 1 and a
vertex in V 2 . ▲

EXAMPLE 10 K 3 is not bipartite. To verify this, note that if we divide the vertex set of K 3 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 K 3 each vertex is connected to every other vertex by
an edge. ▲

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

a b a b
g c
f c
V 1 V 2
v 1 v 2 f
v 3 v 4
e d e d
v
v 5 6
G H
FIGURE 7 Showing That C 6 Is FIGURE 8 The Undirected Graphs G and H.
Bipartite.