Mathematical proofs of two conjectures: The four color problem and the uniquely 4-colorable planar graph. Elecronic Archive

The famous four color theorem states that for all planar graphs, every vertex can be assigned one of 4 colors such that no two adjacent vertices receive the same color. Since Francis Guthrie first conjectured it in 1852, it was until 1976 with electronic computer that Appel and Haken first gave a proof by finding and verifying 1936 reducible unavoidable sets, and a simplified proof of Robertson, Sanders, Seymour and Thomas in 1997 only involved 633 reducible unavoidable sets. Both of proofs could not be realized effectively by hand. Different from related work mentioned above, an alternative method only involving 4 reducible unavoidable sets for proving the four color theorem is used in this paper, which takes form of mathematical proof rather than a computer-assisted proof and proves both the four color conjecture and the uniquely 4-colorable planar graph conjecture by mathematical method. Our work mainly includes the fol-lowing five parts: the first part sets up some basic theory on the chromati