Skip to main content
2 of 5
added 866 characters in body

I don't know about your conjecture, but it does not imply the 4CT. How do you know that your minimal counter-example contains a vertex of degree exactly $5$ ? It's only known that any maximal planar graph contains a vertex of degree at most $5$.

For example the following graph is maximal planar, with max degree $6$, but no vertex of degree exactly $5$.

enter image description here

Note that if you delete the vertex $1$, of degree $6$, then the number of coloring of this new graph is more than $4$ times the number of coloring of the original graph ($192$ and $24$ respectively).

Actually, it's rather easy to construct a maximum planar graph, on $n$ vertices, with degree sequence $\{3,3,4,4,\ldots,4,n-1,n-1\}$. Take a path on $n-2$ vertices $\{1,\ldots,n-2\}$, add a vertex $n-1$ "above" the path, and a vertex $n$ "below" the path, joint each vertex of the path to $n-1$ and to $n$, and finally add an edge $(n-1,n)$. For example on $9$ vertices (don't take into account the vertices' label here)

enter image description here

And I suspect that the conjecture should be easy using some combinatorics arguments : a more general conjecture would be that if you remove a vertex of degree $d$, then you can only multiply the number of possible coloring by $d-1$. But given the graphs above, the value of $d=\min\{\deg(v),\deg(v)>4\}$ over all maximal planar graphs is unbounded.