Where does my short proof of the 4-colour theorem go amiss?

Question

The proof is essentially a generalisation of the $5$-Colour Theorem:

Proof. Consider the set $S$ of planar graphs which are not $4$-colourable. Choose the graph $G \in S$ that has the least number of vertices. If there are multiple such graphs let $G$ denote any one of these arbitrary graphs.

Since $G$ is planar, there exists a vertex $v$ in $G$ such that $deg(v) \leq 5$. Suppose that $deg(v) = 5$; the case $deg(v) = 4$ will follow from this result. If $deg(v) \leq 3$ the result is almost trivial.

Denote the adjacent vertices of $v$ by $x_1, x_2, ..., x_5$. By hypothesis, removing any vertex from $G$ makes the subsequent graph $4$-colourable. As a result, we can colour $G \setminus \{v\}$ with four colours and append $v$ (uncoloured) back afterwards. Since we've just used four colours on the five adjacent $x_i$, it follows that least two must be same colour, say $x_1, x_2$.

We now consider $v, x_2, ..., x_5$ (omitting one of the same-coloured vertices we've just found above). If the remaining $x_i$ are all required to be different colours then there must exist a path between each $x_i, x_j$ with the vertices on this path alternating through the respective colours, otherwise either one of the $x_i, x_j$ can change its colour to match the other. However, as seen in the diagram below, this would contradict the planarity of the graph $G$, which in turn implies that that two of the remaining $x_i$ can indeed share a colour after all. In the diagram above $x_3$ can share the same colour as $x_5$ since they cannot be connected by any path of alternating colours without violating planarity. In this case we then get that $x_1, x_2$ share the same colour (from earlier) and $x_3, x_5$ also share the same colour. The last adjacent vertex $x_4$ is coloured in the third colour, thus allowing $v$ to be coloured in a fourth, providing the necessary contradiction.

However, the diagram above only illustrates one of two possible scenarios. Suppose that again $x_1, x_2$ share the same colour to begin with. Then we omit $x_1$ again, but this time $x_2$ shares colour with one of $x_3, x_4, x_5$ (instead of $x_3$ and $x_5$ as in the diagram above). Then we get that $x_1, x_2, x_3$ all share the same colour, $x_4$ is coloured in the second colour, $x_5$ is coloured in the third colour leaving $v$ to be coloured in the fourth, providing the contradiction again.

Where've I gone wrong?

Answer 1

The proof turns out to be the same as the one provided by Alfred Kempe in 1879. The subtle oversight is that the same-coloured vertex which we first find (namely $x_1$) can in fact turn out to be neighbouring two of the other vertices we deal with in Case 2 above, causing a problem when trying to reduce the adjacent vertices to three colours at the end (as pointed out in a counterexample provided by Percy J. Heawood in 1890).

Answer 2

For your diagram, move $x_3$ below $v$ to the left of $x_5$. Then, we can make a path. You've proven your contradiction with planarity by one example, but it's not true.

After reading the proof you provided in the comments, I think I understand where you went wrong. Lets go through my understanding of your proof. We have the set S of all non 4-colorable planar graphs. We pick $G \in S$, such that G has the least number of vertices possible to be 5 colorable, and by a corollary to Euler's formula (when you write proofs you want to be specific as to where these things come from as this is not immediately obvious at all) the maximum degree of vertex v is $\deg(v) \leq 5$. We select the maximum degree vertex in G, not just any vertex, and we denote the 5 adjacent vertices $x_1, \ldots, x_5$. Regardless, you now claim that we can color G with 4 colors guaranteed, as we chose the minimal vertex graph, and it is now no longer in the set S. Then, you then attempt to claim that this graph must be colorable with less than 4 colors. This is not proven. You argue that we cannot construct a path on between 2, but I don't a path with many vertices and edges. I just need $K_4$, or some equivalency to $K_4$ which is a planar graph. Obviously, there are no counterexamples to this proof, as the theorem is true. But your method of proof assumes that we cannot have a planar graph with a maximal degree of 5, such that if we remove this maximal vertex our induced subgraph is now 4-colorable. This is not proven, and I don't even think it's true.

Regardless still, what do you actually prove? You say if we remove a vertex then we don't need 4 colors, we only need 3. How does that prove you don't need 4 in total? Our vertex that we remove each time could be the reason we go from 4 to 3, and so if we remove it then sure maybe we could do it with 3, but you cant show that we don't need all 4 colors if all 5 vertices are present.

Essentially, you say we have a 4-colorable graph on 5 vertices, 2 must be the same color, remove either of them and then it's 3 colorable. This does not mean our graph on 5 vertices is 3-colorable.