Every Planar Map Is Four Colorable

As has become standard, the four color map problem will be considered in the dual sense as the problem of whether the vertices of every planar graph (without loops) can be colored with at most four colors in such a way that no pair of vertices which lie on a common edge have the same color. The restriction to triangulations with all vertices of degree at least five is a consequence of the work of A. B. Kempe. Over the past 100 years, a number of authors including A. B. Kempe, G. D. Birkhoff, and H. Heesch have developed a theory of reducibility to attack the problem. Simultaneously, a theory of unavoidable sets has been developed and the fusion of these has led to the proof. A configuration is a subgraph of a planar triangulation consisting of a circuit (called the ring) and its interior. A configuration is called reducible if it can be shown by certain standard methods that it cannot be immersed in a minimal counterexample to the four color conjecture. (For details, see [3] or [4].) A set of configurations is called unavoidable if every planar triangulation contains some member of the set. From the definitions, it is immediate that the four color theorem is proved if an unavoidable set of reducible configurations is provided. The most efficient known method of producing unavoidable sets of configurations is called the method of discharging. This method treats the planar triangulation as an electrical network with charge assigned to the vertices. Euler's formula is used to show that the initial charge distribution, giving positive charge to vertices of degree five and negative charge to vertices of degree greater than six, has positive total charge. Next, the initial charge is redistributed in a manner which obeys the principle of conservation of charge. This means that some vertices must end up with positive charge. Such an algorithm can be made sufficiently sophisticated that a finite list of neighborhoods of all possible vertices of ultimately positive charge can be described in detail.