Combinatorics and Probability 741852.(a) We use an argument by contradiction. The idea is to start with Euler’s formula
V−E+F= 2and obtain a relation that is manifestly absurd. By our assumption each vertex belongs
to at least 6 edges. Counting the vertices by the edges, we obtain 2E(each edge has two
vertices). But we overcounted the vertices at least 6 times. Hence 2E≥ 6 V. Similarly,
counting faces by the edges and using the fact that each face has at least three edges, we
obtain 2E≥ 3 F. We thus have
2 =V−E+F≤1
3
E−E+
2
3
E= 0 ,
an absurdity. It follows that our assumption was false, and hence there is a vertex
belonging to at most five edges.
(b) We use the first part. To the map we associate a connected planar graphG. The
vertices ofGare the regions. The edges cross the boundary arcs (see Figure 99). For
a border consisting of consecutive segments that separates two neighboring regions we
add just one edge! The constructed graph satisfies the conditions from part (a). We claim
that it can be colored by 5 colors so that whenever two vertices are joined by an edge,
they have different colors.
Figure 99We prove the claim by induction on the number of vertices. The result is obvious if
Ghas at most 5 vertices. Now assume that the coloring exists for any graph withV− 1
vertices and let us prove that it exists for graphs withVvertices.
By (a), there is a vertexvthat has at most 5 adjacent vertices. Removevand the
incident edges, and color the remaining graph by 5 colors. The only situation that poses
difficulties for extending the coloring tovis ifvhas exactly 5 adjacent vertices and
they are colored by different colors. Call these verticesw 1 ,w 2 ,w 3 ,w 4 ,w 5 in clockwise
order, and assume they are coloredA, B, C, D, E, respectively. Look at the connected
component containingw 1 of the subgraph ofGconsisting of only those vertices colored
byAandC.Ifw 3 does not belong to this component, switch the colorsAandCon this
component, and then colorvbyA. Now let us examine the case in whichw 3 belongs to
this component. There is a path of vertices colored byAandCthat connectsw 1 andw 3.