506
Graphs and Trees
Exercises 65–72 refer to the complement of a graph. If G is a simple graph, the complement of G, denoted G′,
is the simple graph with the same set of nodes as G, where nodes x–y are adjacent in G′ if and only if they are
not adjacent in G.
65. Draw G′ for the graph of Figure 6.18a.
66. Draw K 4 r .
67. Show that if two simple graphs G 1 and G 2 are isomorphic, so are their complements G 1 r and G 2 r .
68. A simple graph is self-complementary if it is isomorphic to its complement. Prove that in a self- complementary
graph with n nodes (n > 1), n = 4k or n = 4k + 1 for some integer k. (Hint: Use the result of Exercise 25.)
69. Prove that in any simple graph G with at least two nodes, if G is not connected, then G′ is connected.
(Hint: If G is not connected, then G consists of a collection of “disjoint” connected subgraphs.)
70. Find a simple graph G with at least two nodes where both G and G′ are connected, thus showing that the
converse of Exercise 69 is false.
71. Given an adjacency matrix A for a simple graph G, describe the adjacency matrix for G′.
72. Prove that if 0 N 0 ≥ 11 in a simple, connected graph G, then not both G and G′ can be planar.
73. Prove that in any simple graph G with n nodes and a arcs, 2a ≤ n
2
− n.
74. Prove that a simple, connected graph with n nodes has at least n − 1 arcs. (Hint: Show that this can be
restated as “A simple, connected graph with m arcs has at most m + 1 nodes.” Then use the second principle of induction on m.)
75. Prove that a simple graph with n nodes (n ≥ 2) and more than C(n − 1, 2) arcs is connected. (Hint: Use
Exercises 69 and 74.)
76. Euler’s formula is stated for simple, connected planar graphs, but in fact the word
“simple” could be omitted.
a. A non-simple graph is a simple graph with loops or parallel arcs added. Prove that
any simple connected planar graph remains a connected planar graph if parallel
arcs or loops are added. (Hint: Temporarily erase the parallel arcs and loops.)
b. Prove that the graph in the figure is a planar graph.
c. Prove that Euler’s formula holds for the graph of part (b) when drawn in its
planar form.
d. Prove that a connected planar graph with parallel arcs or loops obeys Euler’s formula when drawn in
its planar form.
Exercises 77–86 refer to the problem of graph colorability. The origin of graph-coloring problems is a mapcoloring problem: Suppose that a map of various countries, drawn on a sheet of paper, is to be colored so that
no two countries with a common border have the same color. (We need not worry about countries that meet
only at a point, and we will assume that each country is “connected.”) What is the minimum number of colors
required to carry out this task for any map?
77. Show that a coloring of the accompanying map requires three colors and no more than three colors.
78. Draw a map that requires four colors.
Graphs and Trees
Exercises 65–72 refer to the complement of a graph. If G is a simple graph, the complement of G, denoted G′,
is the simple graph with the same set of nodes as G, where nodes x–y are adjacent in G′ if and only if they are
not adjacent in G.
65. Draw G′ for the graph of Figure 6.18a.
66. Draw K 4 r .
67. Show that if two simple graphs G 1 and G 2 are isomorphic, so are their complements G 1 r and G 2 r .
68. A simple graph is self-complementary if it is isomorphic to its complement. Prove that in a self- complementary
graph with n nodes (n > 1), n = 4k or n = 4k + 1 for some integer k. (Hint: Use the result of Exercise 25.)
69. Prove that in any simple graph G with at least two nodes, if G is not connected, then G′ is connected.
(Hint: If G is not connected, then G consists of a collection of “disjoint” connected subgraphs.)
70. Find a simple graph G with at least two nodes where both G and G′ are connected, thus showing that the
converse of Exercise 69 is false.
71. Given an adjacency matrix A for a simple graph G, describe the adjacency matrix for G′.
72. Prove that if 0 N 0 ≥ 11 in a simple, connected graph G, then not both G and G′ can be planar.
73. Prove that in any simple graph G with n nodes and a arcs, 2a ≤ n
2
− n.
74. Prove that a simple, connected graph with n nodes has at least n − 1 arcs. (Hint: Show that this can be
restated as “A simple, connected graph with m arcs has at most m + 1 nodes.” Then use the second principle of induction on m.)
75. Prove that a simple graph with n nodes (n ≥ 2) and more than C(n − 1, 2) arcs is connected. (Hint: Use
Exercises 69 and 74.)
76. Euler’s formula is stated for simple, connected planar graphs, but in fact the word
“simple” could be omitted.
a. A non-simple graph is a simple graph with loops or parallel arcs added. Prove that
any simple connected planar graph remains a connected planar graph if parallel
arcs or loops are added. (Hint: Temporarily erase the parallel arcs and loops.)
b. Prove that the graph in the figure is a planar graph.
c. Prove that Euler’s formula holds for the graph of part (b) when drawn in its
planar form.
d. Prove that a connected planar graph with parallel arcs or loops obeys Euler’s formula when drawn in
its planar form.
Exercises 77–86 refer to the problem of graph colorability. The origin of graph-coloring problems is a mapcoloring problem: Suppose that a map of various countries, drawn on a sheet of paper, is to be colored so that
no two countries with a common border have the same color. (We need not worry about countries that meet
only at a point, and we will assume that each country is “connected.”) What is the minimum number of colors
required to carry out this task for any map?
77. Show that a coloring of the accompanying map requires three colors and no more than three colors.
78. Draw a map that requires four colors.