Section 6.1 Graphs and Their Representations
507
79. Associated with any map is a graph, called the dual graph for the map, formed as follows: Put one node
in each region of the map and an arc between two nodes representing adjacent countries.
a. Draw the dual graph for the map of Exercise 77.
b. Draw the dual graph for the following map.
c. Draw a map for which the following graph would serve as the dual.
80. A coloring of a graph is an assignment of a color to each node of the graph in such a way that no two adjacent nodes have the same color. The chromatic number of a graph is the smallest number of colors needed
to achieve a coloring. Find the chromatic number of the following graphs.
a.
b.
81. At least four colors are required to solve the general map-coloring problem (see Exercise 78). Because no
one could produce a map requiring more than four colors, the conjecture was formulated that four colors
are indeed sufficient. This conjecture became known as the four-color problem. It was first proposed to
the mathematician Augustus De Morgan by one of his students in 1852, and it subsequently received
much attention. It remained unproved, however, for over a hundred years. In 1976 two mathematicians at
the University of Illinois, Wolfgang Haken and Kenneth Appel, used a computer to work through a large
number of cases in a proof by contradiction, thus verifying the four-color conjecture.
The dual graph for a map (see Exercise 79), by the way it is constructed, will always be simple, connected, and planar. In addition, any simple, connected, planar graph can be viewed as the dual graph of
a map. Restate the four-color conjecture in terms of the chromatic number (see Exercise 80) of a graph.
82. Prove that in a simple, connected, planar graph with three or more nodes, there is at least one node with
degree less than or equal to 5. (Hint: Use a proof by contradiction.)
83. (Challenging problem) The five-color theorem states that the chromatic number for any simple, connected, planar graph is at most 5. While the four-color theorem (Exercise 81) is very difficult to prove, the
five-color theorem can be proved by induction on the number of nodes in the graph. Prove the five-color
theorem, making use of the result in Exercise 82.
507
79. Associated with any map is a graph, called the dual graph for the map, formed as follows: Put one node
in each region of the map and an arc between two nodes representing adjacent countries.
a. Draw the dual graph for the map of Exercise 77.
b. Draw the dual graph for the following map.
c. Draw a map for which the following graph would serve as the dual.
80. A coloring of a graph is an assignment of a color to each node of the graph in such a way that no two adjacent nodes have the same color. The chromatic number of a graph is the smallest number of colors needed
to achieve a coloring. Find the chromatic number of the following graphs.
a.
b.
81. At least four colors are required to solve the general map-coloring problem (see Exercise 78). Because no
one could produce a map requiring more than four colors, the conjecture was formulated that four colors
are indeed sufficient. This conjecture became known as the four-color problem. It was first proposed to
the mathematician Augustus De Morgan by one of his students in 1852, and it subsequently received
much attention. It remained unproved, however, for over a hundred years. In 1976 two mathematicians at
the University of Illinois, Wolfgang Haken and Kenneth Appel, used a computer to work through a large
number of cases in a proof by contradiction, thus verifying the four-color conjecture.
The dual graph for a map (see Exercise 79), by the way it is constructed, will always be simple, connected, and planar. In addition, any simple, connected, planar graph can be viewed as the dual graph of
a map. Restate the four-color conjecture in terms of the chromatic number (see Exercise 80) of a graph.
82. Prove that in a simple, connected, planar graph with three or more nodes, there is at least one node with
degree less than or equal to 5. (Hint: Use a proof by contradiction.)
83. (Challenging problem) The five-color theorem states that the chromatic number for any simple, connected, planar graph is at most 5. While the four-color theorem (Exercise 81) is very difficult to prove, the
five-color theorem can be proved by induction on the number of nodes in the graph. Prove the five-color
theorem, making use of the result in Exercise 82.