1

I was browsing a the internet to see if there was a non-computationally intensive proof for the four and sources consistently say that there is not.

Quora: https://www.quora.com/Is-there-a-proof-of-the-Four-Color-Theorem-that-does-not-involve-substantial-computation

Stack Exchange: Is there a simple way to prove the Four Colour Theorem?

However, I've come across a compelling proof that seems to do just that. The gist is that it considers the worst case: fully connected graphs force you to use V different colours where V is the number of vertices. In order to prove the 4CT, they proved that the maximum graph (w.r.t number of nodes) that still maintains planarity has max 4 nodes (max four colours needed). Therefore if you add an extra node to the graph, you could only connect it to 3 out of the 4 nodes from the previous graph while still maintaining planarity. This guarantees that there will always be a colour of the 4 that can be reused.

QUESTION: is this a fake proof?

Link: https://www.researchgate.net/publication/2102948_A_Simple_Proof_of_the_Four-Color_Theorem

If it was valid I feel it would have been well known in academia by now, but the consensus is that the 4CT is yet to be proven in this way.

Misha Lavrov
  • 142,276
Aniekan Umoren
  • 23
  • 2
    There are non-complete planar graphs with more than 4 nodes and chromatic number equal to 4. A new node may be added to such graphs so that it requires connection to more than three nodes and yet the resulting graph is still planar. Your intuition that a simple proof of the four-color theorem that had been around for several years would be well known is correct. – Fabio Somenzi Mar 18 '18 at 05:13

1 Answers1

3

Any proof that talks about the "worst case" for something to hold should immediately be considered suspect. This is not to say that there are never correct proofs that involve a reduction to the worst case. However, at a minimum, all such proofs must:

  • Describe exactly the quantity that the "worst case" is maximizing;
  • Show that cases that are not "worst" can be reduced to worse cases, such that if you solve the worse cases, you solve the original cases as well.

Then, and only then, can a solution to the "worst case" be a general solution. (At that point, the argument becomes a form of proof by induction.)

In the case of the Four-Color Theorem, the problem is that complete graphs (or, more generally, graphs in which $k$ vertices are all connected to each other) are not necessarily a "worst case" for coloring. The Mycielski graphs form a sequence of graphs with ever-increasing chromatic number - they need more and more colors to be properly colored - but none of them even contain $3$ vertices all adjacent to each other.

More generally, random constructions can be used to find graphs which require $1000$ colors to properly color, but in which the shortest cycle has length $1000$ as well: so for any vertex, we can color just the vertices within $499$ steps just with $2$ colors by a greedy approach and not have to deal with any conflicts. This can be done for any value of $1000$.

Of course, the Four-Color Theorem says that none of these graphs which require more than $4$ colors can be planar. But the point is that excluding cliques (groups of vertices, all adjacent to each other) of size $5$ or more does not come close to excluding all configurations that require $5$ or more colors.

Misha Lavrov
  • 142,276