We examine Lord Alfred Bray Kempe's "proof of the Four Color Theorem, from the original faulty publication through several graphs that served as counterexamples throughout the history of the problem. Following Hutchinson and Wagon in [HW98], we then view Kempe's method of proof (literally) as a recursive algorithm, and re-examine our collection of historically motiviated graphs to determine those that are indeed true counterexamples. In particular, Kempe's algorithm may sometimes correctly four color a planar graph and at other times may halt before completing a proper vertex coloring. Penultimately, we present two nine-vertex counterexamples and prove that Kempe's algorithm will never fail to properly vertex color a planar graph on fewer than nine vertices. Finally, we mention some open questions on this subject.
展开▼
