0
$\begingroup$

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. enter image description here 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?

$\endgroup$
6
  • 2
    $\begingroup$ The drawing doesn't demonstrate non-planarity. You can just move $x_3$ to the bottom near $x_5$ and there is no overlap anymore. $\endgroup$ Commented Dec 16, 2023 at 21:16
  • 1
    $\begingroup$ @CyclotomicField You're right, however the diagram is to help with understanding the following statement from the proof: "there must exist a path between each $x_i,x_j$ with the vertices on this path alternating through the respective colours". If we move $x_3$ as you've indicated, we will still end up finding two vertices that cannot be connected as such (since it would end up violating planarity). See this link to a proof of the 5-colour theorem to help: cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/… $\endgroup$
    – David
    Commented Dec 16, 2023 at 21:34
  • 1
    $\begingroup$ No such path is required. For example add three vertices and construct $K_4$ with them and $x_3$. Now it's color is forced but not dependent on any of the other vertices under consideration. $\endgroup$ Commented Dec 16, 2023 at 21:42
  • $\begingroup$ @CyclotomicField when you construct $K_4$ and add $x_3$ to it, note that the colour is forced only if you attach it to all the other $x_i$ which would mean excluding $v$ (otherwise we have $K_5$). But you can't exclude the connection to $v$ because we're operating under the understanding that $x_3$ is adjacent to $v$. Please see the link to the proof of the 5-colour theorem above... $\endgroup$
    – David
    Commented Dec 16, 2023 at 22:00
  • 2
    $\begingroup$ Can someone care to explain the downvotes? I see this as a very good attempt at proving the 4-colour theorem. Yes there are mistakes, but does it deserve the downvotes? @David +1 I upvoted. $\endgroup$
    – IraeVid
    Commented Dec 17, 2023 at 15:00

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hey Robert, please see my response to CyclotomicField's comment above. $\endgroup$
    – David
    Commented Dec 16, 2023 at 21:37
  • $\begingroup$ I edited, your proof is still very confusing even after I read the proof linked to the odd website. Also in the future, take proofs from academic sources, as they are more likely to be correct and teach you better habits about writing proofs. $\endgroup$ Commented Dec 16, 2023 at 23:31
  • $\begingroup$ The link to the webpage is the first result upon searching "5 colour theorem" after the wikipedia article. As for its reliability: it's written by a professor from a reputable university if you check out the webpage a bit more. This is the third time I have to mention this: if you don't understand the proof of the 5 colour theorem you won't understand the proof above. The very beginning of this post states that it's a generalisation of the former. $\endgroup$
    – David
    Commented Dec 17, 2023 at 0:11
  • 1
    $\begingroup$ I understand the proof of the five color theorem, including the proof by contradiction. If you think a well known proof of a theorem (that originated as a failed proof for the four color theorem) can be simply extended to the four color theorem, then I don't think you do. My comment on the website was not that their proof was wrong, it was that it was an odd website. The habits you display in this proof are very non-rigorous which is why I said to read from an academic source to understand a rigorous interpretation of this proof. Your proof is not the 5-color theorem proof extended, it is $\endgroup$ Commented Dec 17, 2023 at 0:24
2
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .