Advanced book on Mathematics Olympiad

742 Combinatorics and Probability

v

w

C

C

A

B

D

B

w

A

A

B

D

D

1

3

w

w 5

w 2

4

C

E

Figure 100

Next, let us focus onw 2 andw 4 (Figure 100). The only case in which we would not
know how to perform the coloring is again the one in which there is a path of vertices
colored byBandDthat joinsw 2 tow 4. Addvto the two paths (fromw 1 tow 3 and
fromw 2 tow 4 ) to obtain two cycles. Because of how we ordered thewi’s and because
the graph is planar, the two cycles will intersect at a vertex that must be simultaneously
colored by one ofAorCand by one ofBorD. This is impossible, so this situation
cannot occur. This completes the solution.

Remark.The famous four color theorem states that four colors suffice. This was first
conjectured by F. Guthrie in 1853, and proved by K. Appel and W. Haken in 1977 with
the aid of a computer. The above five-color theorem was proved in 1890 by P.J. Heawood
using ideas of A. Kempe.

853.We will prove a more precise result. To this end, we need to define one more type of
singularity. A vertex is called a (multi)saddle of index−k,k≥1, if it belongs to some
incoming and to some outgoing edge, and if there arek+1 changes from incoming to
outgoing edges in making a complete turn around the vertex. The name is motivated by
the fact that if the index is−1, then the arrows describe the way liquid flows on a horse
saddle. Figure 101 depicts a saddle of index−2.

Figure 101