Hacker News Reader

Comment by OJFord | Hacker News Reader

I'm not a mathematician, but when I was in school I read a lot of 'pop math', and fancied myself a lot better at it than I was (or am). I was fascinated by things like the FCT, and recall writing a document ...I don't think I kidded myself proving it, but at least 'understanding' it.

The rough sketch was to show that it was not possible to construct a map that required five colours: that if you take a blob of one colour, wrap it in three others, all four are touching the others, but you can't possibly add a fifth since it either only touches the outer three, or it has to prevent two of them touching to get to the inner one (then the non-touching ones could be recoloured the same).

To this day, although I of course realise I was having no groundbreaking thoughts and it did not constitute a proof, I do not understand why the actual proofs are so complex, or require so much computation? It eluded far greater minds for over a century - what am I missing that makes it so problematic?

View on HN

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.

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?

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.

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.

> 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.

I hope that helps.

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

That shows (loosely) that there is no map with five countries that cannot be four-colored. It says nothing about maps with six, seven, etc. countries. An actual map may have billions of countries and need not even contain “a blob of one colour, wrapped in three others”.

Loosely because

a) it only shows it for such maps that contain such a blob. Who says other maps with five countries are easier to four-color?

b) it doesn’t rigorously show it. That you (and me, and everybody who looked at it) can’t find a way to draw that fifth area that touches all others doesn’t say much. what are your arguments for showing you looked hard enough?

For a similar case, read about the Jordan curve theorem. In layman’s terms, it says closed curves on a plane have an inside and an outside part (https://en.wikipedia.org/wiki/Jordan_curve_theorem). Naive readers think it’s so trivial to not require a proof, and it took mathematicians a while to figure out that it needed one. I don’t know the details, but mathematicians may have observed that that theorem also is true on a sphere but isn’t true on a torus (a closed loop ‘around the hole’ in the torus doesn’t have an interior and an exterior). So, they needed an explanation as to why it’s true on a plane or a sphere but not on a torus (the answer essentially boils down to “because a torus has a hole in it”, but that requires a rigorous definition of what a hole is)

If you don't have such a blob then you don't even need four?

This is in the grandparent comment:

"An actual map may have billions of countries and need not even contain “a blob of one colour, wrapped in three others”."

In fact every map of interest will contain a blob wrapped in at least three others.

But they are right that the problem is showing that the theorem holds for maps with billions of regions, or more. Decisions you make early in the process of colouring the map can turn out to be wrong, but only much later as you are trying to colour the last few.

In short, you are saying "I can't see how it can go wrong", but that's not enough ... there are things that might happen that you weren't able to imagine, and that's part of why proofs like this are hard.

Also, the theorem is true, and that makes it hard to explain why it might go wrong. Because we now know that it doesn't.

The grand-parent comment also says:

"... the Jordan curve theorem ... is true on a sphere ..."

The stronger form is not true on a sphere. The stronger form says that every topological sphere in 3-space has an interior that's retractable to a point and an exterior that's retractable to a shell. But the Alexander Horned Sphere[0] is a counter example.

In short, weird things you didn't suspect can happen, so proofs are sometimes harder than you think, even for "obvious" things.

0: https://en.wikipedia.org/wiki/Alexander_horned_sphere

in some sense because there might be strongly non-local effects... an assignment of color in one part of the graph can have an effect on what colors are allowed in a very different part of the graph. Planarity assures some degree of "locality", you can't arbitrarily connect one point to another point.

Your proof sketch actually suggested that it was not possible to construct a map with five regions that require five colours.

Now you need to generalise that to maps with infinitely many regions.

But as a result there could never be an area of an infinitely large map that had five regions each needing a different colour. I understand people are saying but you take two such sub-maps, put them next to each other, and maybe the 'outside' colours are the same - but in that case you could always just recolour them individually before putting them together?

What you've said here might be a reasonable reply in your head, but for me, reading its parent, and this reply, I can't work out what you're trying to say.

You need to be really careful about things like "infinitely large map" ... if you want to talk about really large things then they are really large. But if you want to talk about infinite sized things then you need to be careful. There are traps in infinities, and this theorem is about finite maps (or equivalently, graphs).

Proving that a small, local sub-section doesn't require five colours is helpful, but no one has been able to extend that, because there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem.

You are saying the sorts of things I've seen many times before, but you need to try to make complete, precise statements about exactly what you propose. So far all you've said is that you can't arrange five regions that all touch each other, and that's true. Now, exactly how do you extend that to a map with billions of regions?

It was the comment I replied to that introduced infinitely large maps - but regardless I wasn't trying to be as clever as you might be trying to assume (and of course not finding it :)) - I would have said the same about 'really large' or indeed 'just a bit larger than the 4 or 5 regions I described initially'.

> there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem.

This is the bit I can't grasp - I honestly appreciate the responses and attempts to explain it, but it just (mistakenly, I can accept even if I don't understand) seems counter-intuitive to me. As in, intuitive that it extends, or that there's no such problem.

Maybe I just need to play with it on paper a bit, stumble into such a spooky action to get it.

> Now, exactly how do you extend that to a map with billions of regions?

I don't have the background for the precision you'd like I'm afraid (if I did, I'm sure I'd understand anyway!) but loosely - divide and conquer; a similar thing happens at the interface of all the 'sub-maps'?

>> there is a kind of "spooky action at a distance" that can happen

> This is the bit I can't grasp

OK. Let me give you a collection of statements, each of which I can expand on, but which might give you a sense of the problem.

* Instead of colouring regions in a map we can colour vertices of a graph;

(put a vertex in each region and connect vertices if their regions share a border)

* If a graph can be three-coloured then it can be four-coloured;

(Any three colouring is a four colouring, but with no vertices of the fourth colour)

* An instance of colouring an arbitrary graph can be converted into an instance of colouring a planar graph;

(There is a "widget" that uncrosses edges)

* Given a number to factor, we can construct a graph such that three-colouring the graph will produce a factorisation[0];

(Graph three-colouring is NP-Complete, so this is even easier than that)

Broadly, we can construct a graph that has exactly one (up to permutation of colours) valid three-colouring. As you start to colour it you find that you have to make choices, on average about $4/3$ choices per vertex[1]. But the wrong choice results in not being able to complete the colouring, and you don't know which choice or choices were wrong.

So you get this "spooky action at a distance" thing going on.

Sometimes a planar graph can't be coloured with three colours, and sometimes it can but a colouring is hard to find. When we allow the extra colour it turns out that it's always possible, but it's not obvious that that should be the case.

That's an #ISS-level view of the ideas ... hope it helps.

[0] https://www.solipsys.co.uk/new/FactoringViaGraphThreeColouri...

[1] Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289^n)"[2]

[2] https://en.wikipedia.org/wiki/Graph_coloring#cite_note-15

PS: I've upvoted you because I'm sure other people have the same questions, they're good questions, and they deserve answers.

I'm sure I'm mistaken, but I believe the conversion to a graph loses exactly the information I'm trying to use: a vertex with three edges, where each of those vertices are also all interconnected, can have a fourth edge to a fifth vertex which also has an edge to each of the others; on the map this is not possible. Right?

From my napkin sketch to satisfy myself, I think you can show the same thing equivalently by saying 'and the edges are not allowed to cross' - but I don't know if that's something that exists in graph theory? (If so, it seems to me it should be used here? And if it is, well, finally we have a modicum of precision for what I'm trying to get at!)

Edit: OK, sorry, that is a 'planar graph'.

So, to try to answer your questions:

If you have a map in which you want to colour the regions, you can convert to a graph by putting a capital city in each region, then putting a road between two capitals of countries that share a border. Colouring the capital cities vertices) so that any joined by roads (edges) get different colours is exactly the same problem.

The graph-colouring problem is more general now, but every planar graph is equivalent to a map and vice-versa ... there is a one-to-one correspondence between these problems.

Now we move to the NP-Completeness of the 3-colouring of general graphs. That shows that this sort of thing is hard for the reasons I gave in the grandparent post.

"But" I hear you say "That's for general graphs, and not for planar graphs!"

Yes, but there is a way to convert a graph-colouring problem on a non-planar graph into an equivalent graph-colouring problem on a planar graph, so we neither gain nor lose much by consider just planar graphs.

So 3-colouring planar graphs is NP-Complete.

Then you get into my comments about making bad choices and having to backtrack, and spooky action at a distance.

Hope that helps.

I have no idea what that guy is talking about, but your post reminded me of a fun trick. If you have a colouring of every finite subgraph then you can show the existence of a colouring of the whole graph by using Tychonoff's theorem.

That's cool.

Super cool, but Tychonoff would not have been my first stop here. This seems like a case where it's simplest just to invoke Zorn's lemma directly.

What poset should we set up on which to invoke Zorn's lemma directly? Anything I can think of does seem to me more easily understood via compactness/the ultrafilter lemma, but that may just be a fact about my own psychology.

Use the subgraph relation to define the poset. The big graph is then obviously an upper bound for every chain.

Yes, but invoking Zorn's lemma on that poset does nothing useful. This just proves the trivial fact that the big graph exists. How do you prove that a coloring of the big graph exists?

And if we take the poset to be partial colorings ordered by inclusion, it's not the case that a maximal partial coloring must color the entire graph. Some partial colorings have made choices which prevent them from being extended any further.

[To be clear, whenever I say "coloring", I mean from a fixed set of colors. E.g., a 4-coloring.]

Put another way, it actually is important here that the set of colors we are talking about is finite. It's NOT the case that just having every finite subgraph be C-colorable entails that the entire graph is C-colorable, when C is infinite. For example, if G is the complete graph on an uncountable set of nodes and C is a countably infinite set, then every finite subgraph of G is C-colorable, but G itself is not.

So somewhere in the argument, the finiteness of C must play a role. This is in ensuring compactness.

In short: No.

> there could never be an area of an infinitely large map that had five regions each needing a different colour

A more precise version (infinite -> finite, "...needing a different color looking only at that sub-map) is plausibly true. That doesn't help you though, because...

> maybe the 'outside' colours are the same - but in that case you could always just recolour them individually before putting them together

...this is false. Five patches of one sub-map might touch one patch of the other sub-map. So now you'd have to prove that the first sub-map can be colored with three colors to rescue your proof of the FCT. Further...

> you take two such sub-maps, put them next to each other [...]

...your argument here seems to boil down to "I can construct the full map by gluing together sub-maps". Depending on how you constrain the sub-maps to prove necessary properties (see above), this may not be true. But even if it were, your argument that it works seems to only consider gluing together two sub-maps of specifically size five, which obviously does not allow you to construct maps with more than ten patches.

This makes for two to three fully deal-breaking errors in your proof sketch.

Reply on news.ycombinator.com