**Conjecture:** Let $G$ be a simple maximal planar graph, and let $P(G,4)$ be the number of proper vertex colorings of $G$ with four colors. Let $v$ be a vertex of $G$ with degree ${\rm deg}(v)=5$, and let $G-v$ be the graph obtained after removing that vertex from $G$. Then, we have $P(G-v,4)\leq 4 P(G,4)$, that is, the number of vertex colorings (with four colors) for $G-v$ is at most four times as large than for $G$.

**Question 1:** Is the above result known in the graph theory literature? Where would be a good starting point to find similar results?

**Question 2:** Is the conjecture true? How to prove it?

**Comments:** I believe the conjecture is correct based on numerical verification in many examples. The factor 4 in the inequality is sharp, that is, there exist maximal planar graphs $G$ with ${\rm deg}(v)=5$ such that $P(G-v,4) = 4 P(G,4)$, for example:

(This example has $P(G,4)=24$, and after removal of either one of the degree five vertices we obtain $P(G-v,4)=96$.)

Notice that the truth of this conjecture implies the four-color theorem: Assume the conjecture is correct. Choose $G$ to be a minimal (in the sense of smallest number of vertices) counterexample to the four-color theorem. Assuming that $G$ is maximal planar is without loss of generality (if it is not maximal, then we just add edges until it is). If the minimal degree of $G$ is smaller than five, then there are well-known arguments (Kempe) to derive a contradiction. Thus, existence of $v$ with ${\rm deg}(v)=5$ is without loss of generality. The conjecture then immediately delivers the result $P(G,4)>0$, because we have $P(G-v,4)>0$ (otherwise the counterexample would not be minimal).

fivetimes as large. You want four times as large (which isthreetimes larger). $\endgroup$