A Combinatorial Proof of the Existence of a 4-Coloring for Planar Graphs

A combinatorial tree \ ( (Pt) \) is used to record valid colors to be assigned to each of the vertices of a planar graph \ (G \) of order \ (n \). The main process consists of a loop that incrementally builds \ (G \) vertex by vertex, starting from the most internal triangular face of \ (G \), and in \ (n-3 \) iterations, the paths constructed in \ (Pt \) will have the valid color labels assigned to the vertices of \ (G \). This method ultimately generates all proper 4-colorings of \ (G \). In each iteration, a vertex \ (vᵢ V (G) \) is selected to be aggregated to the current induced subgraph \ (Gᵢ \) of \ (G \). This process, alongside the use of the \ (Pt \) tree (which results in a binary tree of depth \ (n-3 \) ), ensures all proper 4-colorings of \ (G \), regardless of the topology of the maximal planar graph \ (G \). Additionally, we develop an existential theorem that shows that for any maximal planar graph \ (G \), it is always possible to create a proper 4-coloring. Furthermore, we detail a method through which such a 4-coloring can be constructed. Also, we present the extremal topologies of planar graphs, highlighting those with the maximum and minimum number of 4-coloring functions.