Question 3.121

91. When a graph has been drawn on a piece of paper so that edges meet only at vertices, the graph divides the paper up into regions called faces. The faces include one called the “infinite” face, which surrounds the whole graph. The face-coloring number of a graph (which can be drawn in this special way) is the minimum number of colors needed to color the faces of so that two faces sharing an edge receive different colors. (Note that if two faces meet only at a vertex, they can be colored the same color.)

  1. Determine the minimum number of colors needed to color the faces of the accompanying graphs. In each case, remember to color the infinite face, which is labeled (for “infinite”).
    image
  2. Can you think of an application of the problem of coloring the faces of a graph with a minimum number of colors?

91.

(a) Graph (a) 2 (b) 4 (c) 4 (d) 4 (e) 3 (f) 3

(b) Answers will vary.