The Four Color Theorem: A Constructive Proof and a Coloring Algorithm

The Four Color Theorem states that every map drawn on the plane can be colored with four colors such that adjacent regions receive different colors. This paper presents a new, completely human-verifiable proof of this theorem, which does not rely on computer search. The proof is based on embedding an arbitrary planar graph into a triangulation built from two-square cells with diagonals. The main contribution is not only the proof itself but also an explicit coloring algorithm, which is absent from the classic computer-assisted proof by Appel and Haken. The algorithm successively identifies rigid substructures that require a fourth color (''islands'') and colors the remaining part (the ''sea'') with three colors. Special attention is given to clarifying the theorem's formulation: a thought experiment (a 100-meter fence inside a country) demonstrates that the theorem applies only to maps where each region is an independent country in the topological sense and contains no internal boundaries that would require coloring its parts differently.