508
Graphs and Trees
84. The six-color theorem can be proved as a map-coloring problem without using the dual graph. Instead
of creating the dual graph, put nodes at the intersections of boundaries and straighten the boundaries
of regions so that the problem of coloring the map shown in figure (a) is represented by the problem of
coloring the enclosed regions of the graph in figure (b). First assume that no country has a hole in
it. Then the graph will be loop-free, planar, and connected. Also, every node will have degree at
least 3.
(a)
(b)
a. Show that the graph can be assumed to be simple by proving that if six colors are sufficient for coloring
a simple graph, they are sufficient for a graph with parallel arcs as well. (Hint: Use temporary small
countries at nodes.)
b. Prove that in a simple, connected, planar graph with R enclosed regions, n − a + R = 1.
c. Consider a simple, connected, planar graph and assume that every enclosed region has at least six edges
adjacent to it. Show that 2a ≤ 3n − 3.
d. Now consider a simple, connected, planar graph where every node has degree at least 3. Show that such
a graph has at least one enclosed region with no more than five adjacent edges.
e. Prove that six colors are sufficient to color any planar map where no country has a hole in it.
f. Prove that six colors are sufficient to color any planar map. (Hint: Cut some temporary slits in the
map.)
85. Five political lobbyists are visiting seven members of Congress (labeled A through G) on the same day.
The members of Congress the five lobbyists must see are
1. A, B, D
2. B, C, F
3. A, B, D, G
4. E, G
5. D, E, F
Each member of Congress will be available to meet with lobbyists for one hour. What is the minimum
number of time slots that must be used to set up the one-hour meetings so that no lobbyist has a conflict?
(Hint: Treat this as a graph-coloring problem.) What if lobbyist 3 discovers that she does not need to see
B and lobbyist 5 discovers that he does not need to see D?
86. In a multiprocessor machine, six processors labeled A through F share blocks in a common data store. Two
processors cannot simultaneously write to the same block. The following table shows which processors
will write to the data store at the same time. How many distinct blocks are needed? (Hint: Treat this as a
graph-coloring problem.)
A, F, C
B, D
F, D, A
B, E
F, C, E
Graphs and Trees
84. The six-color theorem can be proved as a map-coloring problem without using the dual graph. Instead
of creating the dual graph, put nodes at the intersections of boundaries and straighten the boundaries
of regions so that the problem of coloring the map shown in figure (a) is represented by the problem of
coloring the enclosed regions of the graph in figure (b). First assume that no country has a hole in
it. Then the graph will be loop-free, planar, and connected. Also, every node will have degree at
least 3.
(a)
(b)
a. Show that the graph can be assumed to be simple by proving that if six colors are sufficient for coloring
a simple graph, they are sufficient for a graph with parallel arcs as well. (Hint: Use temporary small
countries at nodes.)
b. Prove that in a simple, connected, planar graph with R enclosed regions, n − a + R = 1.
c. Consider a simple, connected, planar graph and assume that every enclosed region has at least six edges
adjacent to it. Show that 2a ≤ 3n − 3.
d. Now consider a simple, connected, planar graph where every node has degree at least 3. Show that such
a graph has at least one enclosed region with no more than five adjacent edges.
e. Prove that six colors are sufficient to color any planar map where no country has a hole in it.
f. Prove that six colors are sufficient to color any planar map. (Hint: Cut some temporary slits in the
map.)
85. Five political lobbyists are visiting seven members of Congress (labeled A through G) on the same day.
The members of Congress the five lobbyists must see are
1. A, B, D
2. B, C, F
3. A, B, D, G
4. E, G
5. D, E, F
Each member of Congress will be available to meet with lobbyists for one hour. What is the minimum
number of time slots that must be used to set up the one-hour meetings so that no lobbyist has a conflict?
(Hint: Treat this as a graph-coloring problem.) What if lobbyist 3 discovers that she does not need to see
B and lobbyist 5 discovers that he does not need to see D?
86. In a multiprocessor machine, six processors labeled A through F share blocks in a common data store. Two
processors cannot simultaneously write to the same block. The following table shows which processors
will write to the data store at the same time. How many distinct blocks are needed? (Hint: Treat this as a
graph-coloring problem.)
A, F, C
B, D
F, D, A
B, E
F, C, E