Every planar map is four colorable. Part I: Discharging

Abstract

produced a map M, with r polygons by erasing from M,+ one edge in the boun- dary of an appropriate Pk.By the induction hypothesis, M, admits a four coloring, say cr, and Kempe attempted to derive a four coloring cr+l of Mr+ from cr.This task was very easy in the cases of Pz and P3.Totreat the cases of P4 and Ps, Kempe invented the method of interchanging the colors in a maximal connected part which was colored by cr with a certain pair of colors (two-colored chains were later called Kempe chains) to obtain a coloring c'r of Mr from which one can then obtain a four coloring G+ of Mr+ 1.While Kempe's argument was correctly applied to the case of P4, it was incorrectly applied to the case of P5 as was shown by Heawood [-18"1 in 1890.Kempe's argument proved, however, that five colors suffice for coloring planar maps and that a minimal counter-example to the Four Color Conjecture (minimal with respect to the number p of polygons in the map) could not con- tain any two-sided polygons, triangles, or quadrilaterals.This restricts the Four Color Problem to the consideration of normal planar maps in which each polygon has at least five neighbors.Each such map must contain at least twelve pentagons since in (1.1) we have P2 P3 P4 0 and thus kma (1.2) Ps 2 (k-61p k + 12.k=7 Since 1890 a great many attempts have been made to find a proof of the Four Color Theorem.We distinguish two types of such attempts" (i) attempts to