Page 676 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 655

EXAMPLE 5 Complete Graphs A complete graph on n vertices, denoted by K n , is a simple graph
that contains exactly one edge between each pair of distinct vertices. The graphs K n , for
n = 1, 2, 3, 4, 5, 6, are displayed in Figure 3. A simple graph for which there is at least one
pair of distinct vertex not connected by an edge is called noncomplete. ▲

K 1 K 2 K 3 K 4 K 5 K 6
FIGURE 3 The Graphs K n for 1 ≤ n ≤ 6.

EXAMPLE 6 Cycles A cycle C n , n ≥ 3, consists of n vertices v 1 , v 2 ,..., v n and edges {v 1 , v 2 },
{v 2 , v 3 },..., {v n−1 , v n }, and {v n , v 1 }. The cycles C 3 , C 4 , C 5 , and C 6 are displayed in
Figure 4. ▲

C 3 C 4 C 5 C 6

FIGURE 4 The Cycles C 3 , C 4 , C 5 , and C 6 .

EXAMPLE 7 Wheels We obtain a wheel W n when we add an additional vertex to a cycle C n , for n ≥ 3,
and connect this new vertex to each of the n vertices in C n , by new edges. The wheels W 3 , W 4 ,
W 5 , and W 6 are displayed in Figure 5. ▲

W 3 W 4 W 5 W 6

FIGURE 5 The Wheels W 3 , W 4 , W 5 , and W 6 .

EXAMPLE 8 n-Cubes An n-dimensional hypercube,or n-cube, denoted by Q n , is a graph that has vertices
n
representing the 2 bit strings of length n. Two vertices are adjacent if and only if the bit strings
that they represent differ in exactly one bit position. We display Q 1 , Q 2 , and Q 3 in Figure 6.
Note that you can construct the (n + 1)-cube Q n+1 from the n-cube Q n by making two
copies of Q n , prefacing the labels on the vertices witha0inonecopyof Q n andwitha1inthe
other copy of Q n , and adding edges connecting two vertices that have labels differing only in
the first bit. In Figure 6, Q 3 is constructed from Q 2 by drawing two copies of Q 2 as the top and
bottom faces of Q 3 , adding 0 at the beginning of the label of each vertex in the bottom face and
1 at the beginning of the label of each vertex in the top face. (Here, by face we mean a face of
a cube in three-dimensional space. Think of drawing the graph Q 3 in three-dimensional space
with copies of Q 2 as the top and bottom faces of a cube and then drawing the projection of the
resulting depiction in the plane.) ▲