Page 678 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 657

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 for G to 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 that G = (V, E) is a bipartite simple graph. Then V = V 1 ∪ V 2 , where V 1
and V 2 are disjoint sets and every edge in E connects a vertex in V 1 and a vertex in V 2 .Ifwe
assign one color to each vertex in V 1 and a second color to each vertex in V 2 , 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 V 1 be the set of vertices
assigned one color and V 2 be the set of vertices assigned the other color. Then, V 1 and V 2
are disjoint and V = V 1 ∪ V 2 . Furthermore, every edge connects a vertex in V 1 and a vertex
in V 2 because no two adjacent vertices are either both in V 1 or both in V 2 . Consequently, G
is bipartite.

We illustrate how Theorem 4 can be used to determine whether a graph is bipartite in
Example 12.

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. ▲

Theorem 4 is an example of a result in the part of graph theory known as graph colorings.
Graph colorings is an important part of graph theory with important applications. We will study
graph colorings further in Section 10.8.
Another useful criterion for determining whether a graph is bipartite is based on the notion
of a path, a topic we study in Section 10.4. A graph is bipartite if and only if it is not possible
to start at a vertex and return to this vertex by traversing an odd number of distinct edges. We
will make this notion more precise when we discuss paths and circuits in graphs in Section 10.4
(see Exercise 63 in that section).