It's (relatively) easy to prove that you can't have five regions that all touch each other. If you could then that would mean that a map requires (at least) five colours, but that's not the only way a map could require five colours. Even so, it's certainly the first thing to try.
But colours-at-distance can be forced, so proximity isn't needed to create the need for another colour.
The theorem is difficult for two meta-reasons. One is that there are arbitrarily many planar configurations, and you need to prove that they are all four-colourable. The other is that whether or not a planar graph is three colourable is NP-Complete, and showing a planar graph is five-colourable is fairly easy, so it's on the boundary between fairly easy and really hard.
The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
Appel and Haken's proof of the four-colour theorem proceeded the same way, but the unavoidable set was large. The computation was to confirm that the set was unavoidable, and that each element was reducable. This involved a huge amount of tedious bookkeeping, best done by machine, but it was really just "doing the sums". The real work was creating a finite amount of bookkeeping that would then constitute a proof.
>The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
Isn't this missing a crucial point? You seem to be saying:
1. There is some (small) set S of graphs, all of which are 5-colorable
2. Every planar graph has at least 1 sub-graph in S
3. Therefore, all planar graphs are 5-colorable
But, from statements 1 and 2, one can only conclude that every planar graph _has a sub-graph_ that is 5-colorable, not that the entire graph is 5-colorable.
Don't you also need to prove that the complement of the sub-graphs is 5-colorable?
> The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example.
You said:
> Isn't this missing a crucial point? You seem to be saying:
> 1. There is some (small) set S of graphs, all of which are 5-colorable
This is not what it's saying. It's saying that these graphs cannot be in a minimal counter-example. That's different from simply saying that they are 5-colourable.
> 2. Every planar graph has at least 1 sub-graph in S
> 3. Therefore, all planar graphs are 5-colorable
No, you've missed a bit of my comment. I said:
> showing for each of those that it cannot be in a minimal counter example.
So we have an unavoidable set U. So for every graph G there is an element S of U that is a sub-graph of G.
But we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example. We're not showing that these elements S of U are themselves 5-colourable, we are showing that any G containing S is not a counter-example to the theorem.
So now suppose the theorem is false. That means there is a graph that requires 6 colours. From among those choose a minimal one, so M is a minimal counter-example. But the set U is unavoidable, so there is a S in U that is a subgraph of M. But any graph containing S cannot be a minimal counter-example, and we have our contradiction.
Hence there are no counter-examples, and the theorem is true.
For the Five Colour Theorem the unavoidable set U has only four graphs, so it's easy to check by hand. For the Four Colour Theorem in the original proof there were around 2000 elements of U, so it was infeasible to check by hand. That has been reduced to 633 graphs in U, but it's still tough to check by hand.
The paper in the original submission here takes a different approach.
> I read "those" as "those subgraphs" rather than "those graphs".
That is the correct reading; your mistake must be elsewhere?
>> [the proof] proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example.
No minimal counterexample to the claim [that a planar graph is 5-colorable] can contain any of these subgraphs. All planar graphs contain at least one of these subgraphs. Therefore, all planar graphs fail to satisfy the predicate "this graph is a minimal counterexample to the claim that all planar graphs are 5-colorable".
The elaboration is very explicit that the theorem is "for every subgraph S in the unavoidable set U, that subgraph (S) cannot be contained in any minimal counterexample":
>> we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example.
As the sibling comment to this says, you must still be confused about something here. Let me expand.
The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds as follows.
Cleverly produce a set U of small graphs S that have the following properties:
1: For every graph G, there is an S in U such that S is a sub-graph of G;
2: If G is a counter-example to the theorem, and S from U is a sub-graph of G, then there is a smaller graph H that is also a counter-example.
This is enough, because now let M be a minimal counter-example. By (1) there is an S from U that is a sub-graph of M. But by (2) there is then a smaller counter-example, contradicting the minimality of M. So there can be no counter examples.
With that now in mind, here is the original statement:
We proceed by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
You don't just show that the graphs in S are 5-colourable. You show that they couldn't possibly be part of a minimal non-colourable graph (e.g. if a graph containing this subgraph is not 5-colourable, you can replace this subgraph with this simpler subgraph, and the larger graph will still be non-5-colourable).
But colours-at-distance can be forced, so proximity isn't needed to create the need for another colour.
The theorem is difficult for two meta-reasons. One is that there are arbitrarily many planar configurations, and you need to prove that they are all four-colourable. The other is that whether or not a planar graph is three colourable is NP-Complete, and showing a planar graph is five-colourable is fairly easy, so it's on the boundary between fairly easy and really hard.
The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
Appel and Haken's proof of the four-colour theorem proceeded the same way, but the unavoidable set was large. The computation was to confirm that the set was unavoidable, and that each element was reducable. This involved a huge amount of tedious bookkeeping, best done by machine, but it was really just "doing the sums". The real work was creating a finite amount of bookkeeping that would then constitute a proof.