278 16. Answers to Exercises
13 Coloring Maps and Graphs
13.1 Coloring Regions with Two Colors
13.1.1. By induction. True ifn= 1. Letn>1. Assume that the descrip-
tion of the coloring is valid for the firstn−1 circles. If we add thenth, the
color and the parity don’t change outside this circle; both change inside
the circle. So the description remains valid.
13.1.2. (a) By induction. True for 1 line. Adding a line, we recolor all
regions on one side.
(b) One possible description: Designate a direction as “up.” Letpany point
not on any of the lines. Start a half-line “up” fromP. Count how many of
the given lines intersect it. Color according to the parity of this intersection
number.
13.2 Coloring Graphs with Two Colors
13.2.1. This graph cannot contain any odd cycle. Indeed, if we consider
any cycleC, then each edge of it contains exactly one intersection point
with the union of circles. The contribution of every circle is even, since
walking aroundC, we cross the circle alternatingly in and out.
13.3 Coloring Graphs with Many Colors
13.3.1. Suppose that we have a good 3-coloring of the first graph. Starting
from above, the first vertex gets (say) color 1, the vertices on the second
level must get colors 2 and 3, and then both of the lowest two vertices must
get color 1. But this is impossible, since they are connected.
Suppose that we have a good 3-coloring of the second graph. Starting from
the center, we may assume that it has color 1, so its neighbors get colors 2
or 3. Now recolor each outermost vertex with color 1 by giving it the color
of its inner “twin”. This coloring would give a good coloring of a 5-cycle
by 2 colors, since “twins” have the same neighbors (except that the inner
twin is also connected to the center). This is a contradiction.
13.3.2. By rotating the plane a little, we may assume that all intersection
points have differentycoordinates (which we just call “heights”). Starting
with the highest intersection point, and moving down, we can color the
intersection points one by one. Each time, there are at most two intersection
points that are adjacent to the current point along the two lines that were
colored previously, and so we can find a color for the current point different
from these.
13.3.3. We may assume that there are at least 2 nodes, and so there is
a node of degree at mostd. We delete it, recursively color the remaining