Hacker News Reader

Comment by whoopdedo | Hacker News Reader

I've never understood why the proof had to be so complicated.

Instead of color filled areas, use nodes and arcs. One and two nodes are trivial. When you add a third node it either connects to one other node and then can be just a second color, or it connects to both and you have an enclosed region (two actually). When you add the fourth node it will have a fourth color if it has three arcs. You now have 6 arcs which is the maximum possible with four nodes. To reiterate, a map the requires three colors has three nodes and three arcs; a map the requires four colors has four nodes and 6 arcs. So a map that would require five colors should have five nodes and ten arcs. But that's not possible.

View on HN

"I've never understood why the proof had to be so complicated."

Others are trying to explain, but I'd point out, as the article observes, this is very accessible math. If you really want to know, sit down and try it.

The only warning I'd give is that this is an extraordinarily well-examined problem, so I'd encourage you as strongly as I can that if you think you found a simple proof that you leap to the conclusion that you must be missing something, and then go searching for that something, rather than believing that you've found the simple proof.

I'm being serious, not sarcastic at all. This sort of thing is really quite educational, with counterexamples literally producible with a bit of doodling and four colors of pen, and can be quite fun, and this is far more accessible than many such mathematical exercises.

> a map the requires four colors has four nodes and 6 arcs

That's not the only case - there are an infinite number graphs that require 4 colors. It's possible that all of them have a subgraph with four nodes and 6 edges connecting them, but I don't know either way.

> So a map that would require five colors should have five nodes and ten arcs

How do you know there isn't a graph with 35 nodes and 127 edges that requires 5 colors?

That's the local part. What you have to show is that for any configuration you can't "paint yourself into a corner."

The standard proof does use nodes and arcs (or vertices and edges, which I am taking to mean the same thing). A proper coloring must assign distinct colors to neighboring vertices, but this doesn't mean that vertices with the same color are identified.

Here's an overview of the simplest version of the proof as of 1998: http://www.ams.org/notices/199807/thomas.pdf . This should shed some light on why the proof is as complicated as it is. (See especially the section on equivalent formulations.)

I'm way out of date. The proof (discretized using hypermaps instead of graphs) was completely formalized in Coq in 2005: http://research.microsoft.com/en-us/um/people/gonthier/4colp...

Reply on news.ycombinator.com