3 ms·

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) fiv

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.

siftrics 4y ago
Thanks for the insightful comment. >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?
- ColinWright 4y ago
  My comment was: > 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.
  - siftrics 4y ago
    Ah, thank you. The key to my misreading was this part: > showing for each of those that it cannot be in a minimal counter example I read "those" as "those subgraphs" rather than "those graphs". Thanks.
    - thaumasiotes 4y ago

siftrics 4y ago

Thanks for the insightful comment. >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?

ColinWright 4y ago
My comment was: > 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.
- siftrics 4y ago
  Ah, thank you. The key to my misreading was this part: > showing for each of those that it cannot be in a minimal counter example I read "those" as "those subgraphs" rather than "those graphs". Thanks.
  - thaumasiotes 4y ago