[jordigh]

   You never need more than four colors to color every country
   on a map a different color from its neighbours. This was
   proved in the 20th century — but nobody knows why it is true.

Heh. I suppose we've proved it, but this author doesn't accept this proof as an explanation for why it's true.

[JadeNB]

> Heh. I suppose we've proved it, but this author doesn't accept this proof as an explanation for why it's true.

I think that this is a reasonable philosophical position; given the heavily computer-based nature of the proof, even mathematicians who might accept that (say) the proof of the solubility of odd-order groups explains 'why' they are soluble are reluctant to accept this (the 4-colour proof) as a 'true' explanation.

Even if you have no problem with computer-generated proofs, I think that there is a big gap, for professionals and amateurs alike, between proof and explanation.

[Someone]

"You never need more than four colors to color every country on a map a different color from its neighbors"

Is that true in today's geography? I know of one almost [1] counterexample (of that specific statement, not of the four-color theorem): the North Sea, Belgium, the French Republic, Germany and the Kingdom of the Netherlands all border each other, so you need five different colors to color them on a map.

[1] Almost because the Kingdom of the Netherlands isn't a country.

Confused? Read http://en.m.wikipedia.org/wiki/Kingdom_of_the_Netherlands, in particular the part about overseas territories, and notice that Sint Maarten borders Saint-Martin.

[on an even more sideways track: the US dollar is an official currency in part of the _country_ of the Netherlands (in Bonaire, Saba and St Eustatius)]

Back to my original question: does anybody know of a valid counterexample for the statement on countries?

[JadeNB]

> [1] Almost because the Kingdom of the Netherlands isn't a country.

Neither is the North Sea! Nonetheless, this is a neat example.

> Back to my original question: does anybody know of a valid counterexample for the statement on countries?

A standard counterexample to the hypotheses of the 4-colour theorem (though not to the conclusion, as consulting a map easily verifies) is Michigan, which is not connected.

The 4-colour theorem's hypotheses also rules out the possibility of 4 countries meeting at a corner (or, rather, declare that they don't meet in that case). If there were such an arrangement—and I'd be surprised if there isn't; for 3 countries, one has the example of Finland, Sweden, and Norway—then it would be easy to juice it up to a counterexample.

Maybe the guy who established an island with a bizarre currency, including one coin that had a denomination of π (I can't remember who—I thought Dean Kamen, but his Wikipedia page doesn't mention it), could be induced to subdivide his island in such a way as to create a counterexample. :-)

[Someone]

According to http://en.m.wikipedia.org/wiki/Quadripoint, there currently isn't any quadripoint between countries, although it is awfully close between Namibia, Botswana, Zambia and Zimbabwe.

Trijunctions are very common. Luxembourg has 3 of them, Germany (if I count correctly) 7.

[JadeNB]

Wow—regardless of its use to answer the question, that's a new word for me, and a fascinating article. (Who would have expected such a debate to lead to literal shots fired? Well, I guess any student of cartography and history, but not me.) Thanks!

[dedward]

I was under the impression corners don't matter... it's about borders, not corners. Draw any kind of map you like, you only need four colours.

[JadeNB]

> I was under the impression corners don't matter... it's about borders, not corners. Draw any kind of map you like, you only need four colours.

Corners matter (or do not matter, depending on how you like to phrase it!) only in the slightly non-intuitive sense that countries that meet only at a corner must be declared not to 'meet' at all for purposes of the theorem. Otherwise, you can have four regions meeting only at a corner (say by sub-dividing a square), which therefore use 4 colours, and a 'moat' surrounding them all, which therefore requires a 5th colour.

[Someone]

Or just n>4 regions meeting in a corner. Allowing 'meeting in a single point' turns the theorem into the 'infinite color theorem', which would be uninteresting.

[dedward]

Right.

The point I'm making is that this isn't simply that "there isn't anything in our current geo-political makeup where enough countries meet to disprove the theorem"... the theorem holds up under any theoretical design.

[JadeNB]

As a geographical idiot who has just consulted a map, I am puzzled by:

> I know of one almost [1] counterexample (of that specific statement, not of the four-color theorem): the North Sea, Belgium, the French Republic, Germany and the Kingdom of the Netherlands all border each other, so you need five different colors to color them on a map.

On Google Maps, Belgium seems to interpose entirely between France and the Netherlands. Am I deceived by appearances, or is there some subtle geopolitical point?

[Someone]

Read my post again, especially the part after Confused?

The kingdom of the Netherlands borders the French Republic in the Caribbean.

[JadeNB]

Ah—I knew (because the 4-colour theorem holds!) that there must be a meeting at a corner or a disconnection, but I couldn't see either! Thanks for clarifying.

[sebastialonso]

The "proof" you're most likely talking about doesn't show why this is true. Merely shows that it is true.

Exhaustion doesn't qualify as a real argument, in my opinion.

[wetmore]

People often talk about the proof as if they just enumerated every possible planar graph and checked. Which is true in a sense, but disregards the work that went into making it possible to enumerate the cases in the first place.

There are infinitely-many possible planar graphs, so you of course need to find some invariants that allow you to bring the necessary number of graphs to check to be finite. Beyond that, the techniques in the 4CT which make it actually possible to reduce the number of cases to a feasibly enumerable number are very clever and require some insight.

[jordigh]

Proof by exhaustion is considered a real argument as long as there are not too many cases to exhaust. One of the most dramatic examples is the proof of that result that goes... if RH is true, then the result is true. If RH is false, then the result is true. Therefore, the result is true!

So, why make the cut-off point of when exhaustiong is an explanation at some finite number of cases?

[GFK_of_xmaspast]

Personally, I think it's totally valid. (PhD mathematician here).

[JadeNB]

> Personally, I think it's totally valid.

To be fair, though it's a bit ambiguous, I read sebastialonso's post https://news.ycombinator.com/item?id=8799362 as indicating that he or she believes that the result is true—i.e., does not necessarily reject the validity of proof by exhaustion as a style of argumentation—but does not feel that the proof by exhaustion is an explanation.

[evanb]

It's certainly a valid argument, but it's not... enlightening in the same way other kinds of arguments are.