Show that $G$ has a 4-colouring

Question

Without using the four color theorem, prove that if $G$ is a planar graph such that every proper subgraph of G has a 4-coloring and such that G has a vertex of degree 4, then $G$ has a 4-coloring.

I managed to show that if a 4-coloring does not exist, then the minimum degree of $G$ is 4, but I don't think this is useful. The only criteria about planar graphs that I know of is Euler's Formula.

Answer 1

For this problem, we will need an honest-to-goodness plane embedding of $G$, where the vertices are dots on the plane and the edges are curves connecting the dots. Choose $v$ to be a vertex with degree $4$, and let its neighbors in the plane embedding be $a,\ b,\ c,\ d$ in clockwise order. We are told that $G-v$ is $4$-colorable, so choose such a coloring with vertex colors red, green, blue, and yellow. Our goal is to show that $G$ also has an admissible $4$-coloring.

If any of $a,\ b,\ c,\ d$ have the same color, then we can trivially color $v$ one of the missing colors and we are done. So let us assume that the four vertices all have different colors. Without loss of generality, we may assume that the graph looks like this:

Let $V'$ be all of the vertices colored red or blue, and let $H=G[V']$ be the subgraph induced by those vertices. We now have two possibilities: either $a$ and $c$ are in the same component of $H$ or they are not.

• If they are not, then let $H'$ be the component of $H$ that contains $a$. We will recolor the vertices in $H'$ by switching all of the red vertices to blue and vice-versa. This is still an admissible $4$-coloring in $G-v$; for instance, if any red vertex in $G-v$ is next to a new red vertex from $H'$, then that old red vertex would have been in the same component of $H$ and would have been switched to blue, a contradiction. However, with this recoloring, $a$ and $c$ are now both blue, allowing us to color $v$ red, completing an admissible $4$-coloring of $G$.
• If $a$ and $c$ are in the same component, then there is a path of alternating red-blue vertices connecting them something like this:

Now, do the same trick as before, except the subgraph induced by all the yellow and green vertices. This time, we do not get the luxury of contemplating that there is a yellow-green path connecting $b$ and $d$, because in a plane graph they would be unable to cross the red-blue path connecting $a$ and $c$. (This is leaning on the Jordan Curve Theorem, which is an intuitively obvious but surprisingly non-trivial theorem of topology.) Therefore, similar to the previous case, we can switch the colors of the yellow and green vertices in the component that $b$ is in and then color $v$ green to complete an admissible $4$-coloring of $G$.

Therefore, we have covered all of the possible cases, and in each we were able to create and admissible $4$-coloring of $G$. Since $G$ was an arbitrary planar graph with a vertex with degree $4$, the theorem holds.