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_i \in V(G) \) is selected to be aggregated to the current induced subgraph \( G_i \) 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.