Maths people please - 4 colour map theory

In My Humble Opinion (IMHO)
#1

This theory says that any flat map of interconnecting lines may be coloured using only 4 distinct colours, such that no two ajoining areas have the same colour.

As far as I know, this theory has not been proven. Not being mathematically minded, I’m just wondering why it isn’t possible to prove this? I mean, no-one has ever created a map which can’t be coloured using just 4 colours, have they? I would have thought, especially with the aid of fast computers, that this theory would have been proven by now.

#2

On second thoughts this should probably be in General Questions. Sorry if its in the wrong forum.

#3

This has been proven, though I do not know nor understand the proof.

However, most people think of map they are including other things such as water and countries that are split in two by another countr, ie Alaska and the rest of the US. When that happens then no you may not be able to use only four colors. You can prove this yourself if you really really want to by using just the lower 48 states and you can color them in only 4 colors. The reason is that you can not have five shapes, that are not broken, touch each of the other shapes at least once. Basically you nead A touching B, A touching C, A touching D, A touching E, B touching C, etc. At some point two will not be able to touch.

As I said using an everyday map will not help, nor will it work, because of countries that are split and of water. Which is why maps are usually 5-6 colors.

#4

Some restrictions on the four color theory:

  1. Each “country” must be contiguous (so no Alaska-type situations allowed).

  2. Each adjacent country must not have a positive-length border with another of the same color. Note that this does not preclude sharing a corner (a zero-length border.)

Maps can be represented as simple graphs, with each country a dot, and lines connecting the dots that represent the countries which share a border.

There is a good page on the four color theorem at Wikipedia here and also Cecil’s column here.

#5

Actually, it’s not really as simple as that. This statement about five shapes would be fairly easy to prove, while the four color theorem is notoriously difficult. The problem is, what if you have a map with, say, 1000000 different countries (or even some larger number)? It may be true that no five of them are all mutually adjacent, but maybe, over the “totality” of their boundaries, somewhere down the line, five colors are still required to color all of them.

Here’s a Straight Dope column on Haken and Appel’s proof of the four color theorem, and why the proof isn’t as satisfactory as might be hoped for.

#6

The 4-color map problem is one that I find interesting, just because it can be stated formally in one page, but the shortest known proof is probably over 2,000 pages long. There’s no reason to believe that a shorter proof exists.

#7

Here’s an interesting site on the subject:

http://www.math.gatech.edu/~thomas/FC/fourcolor.html

#8

The four colour theorem was an interestiong conjecture, but even more interesting was the way it redefined the nature of proof. It is for that reason that it is still discussed.

The proof does not consist of a logical argument in the classical sense. Instead it is an exhaustive search by computer of all possible configurations and a demonstariion of four-colourness for each. The arguments against it are as follows:

  1. can we guarantee that all possible base configurations have been correctly categorised and accounted for. The sheer size of the task makes it difficult to check manually (which is why a computer was used in the first place.)
  2. If there is no one who can actually verify every line of the proof, is it actually a proof?

The concensus in the mathematical world is that the theorem has been proved and the proof is valid. But that doesn’t mean that it didn’t provoke a lot of discussion and deep thinking when it was first published.

#9

You’re right that it’s not a logical proof, j_sum1. And of course, there are an infinite variety of maps since we can have an infinite amount of space and an infinite number of countries. The proof only proves that every case they tested could be four-colored, but the sample is big enough, and representative enough of maps in general, that it is reasonable to conclude that the argument is sound.

#10

friedo - words like “the sample is big enough, and representative enough of maps in general” are fine in statistics, but wouldn’t be accepted by mathematicians for an instant in a proof. As j_sum1 said, the claim of the 4CT proof is that the enumeration of possible configurations was exhaustive - that is, complete, not missing any possibilities.

I’m personally willing to take their word for it - well, the word of them and the other mathematicians who’ve checked out the various parts of it. AFAIK, the whole thing has been verified, but just not by any one person, because it’s too big.

#11

I don’t think it is a case of it being statistically representative that is the issue here. What is the issue is determining whether the cases that were computer tested were exhaustive of all possible categories. Verifying that is the essence of the proof and no mean feat.

#12

RTFirefly – snap!!
simulpost

#13

It is a logical proof, by a method known as perfect induction (the fancy term for brute force).

The gist of it is that we start knowing that in any case, one of A[sub]1[/sub], A[sub]2[/sub], …, A[sub]n[/sub] is true.

If we assume A[sub]1[/sub], we can show that it implies B.

If we assume A[sub]2[/sub], we can show that it implies B.

…

If we assume A[sub]n[/sub], we can show that it implies B.

Therefore, B is true if any one of A[sub]1[/sub], A[sub]2[/sub], …, A[sub]n[/sub] is true, and we know that they’re never all false, so we can conclude B.

#14

If you want to be famous, find a counter example that proves the theorem is false. :slight_smile: