[umvi]

Seems easy to intuitively prove that 5 colors is impossible.

In order to need 5 colors, you'd need to construct a graph with 5 nodes where each of the nodes connects to all other nodes, but without any edges crossing: https://imgur.com/U52SFSi

You can just tell after playing around with the graph that it's impossible to move the nodes around on a 2d plane without an edge crossing; you need a 3rd dimension.

[tomsmeding]

Why would it be necessary for a graph requiring 5 colours to have a 5-clique (as it's called [1])? The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours. (Try drawing out the incidence graph of the faces, i.e. a vertex is a US state and an edge is two states bordering. Lots of 3-cliques (triangles), but no 4-clique!)

Side note: indeed, 5-cliques are not planar: that is to say, there is no map you can draw that has five regions all bordering each other. This is not too difficult to prove, actually. Proving that 4 colours is enough is a whole different league!

[1]: https://en.wikipedia.org/wiki/Clique_(graph_theory)

[2]: https://www.rahulilango.com/coloring/wus

[umvi]

"The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours."

It has something very similar to a 4-clique that can be simplified to a 4-clique for the purposes of the coloring exercise: https://imgur.com/a/oRJBkFp

Or more generally, if you have any hub-and-spoke topology with an odd number of spokes, it can be simplified to a 4-clique and have the same properties.

So I concede that a graph requiring 5 colours doesn't have to have a 5-clique exactly, but it needs something that is either a 5-clique or can be simplified to a 5-clique.

I'm not a graph theory expert, so I'm assuming the complexity of the colors proof comes from the difficulty of being able to simplify complex graphs into simple atoms/cliques.

[JohnKemeny]

Impressive deduction from someone not into graph theory, but what you're saying is actually known as the Hadwiger conjecture. It says that if a graph isn't t-colorable, then it must have K_t as a minor, where the concept of minor is what you mean (perhaps) with "simplified to".

It so happens that planar graphs are K_5 minor free.

This is touching in on extremely deep theory in the graph theory field.

[SamBam]

I've always found what happens in the third dimension weird.

A 0-dimensional space needs up to: 1 color.

A 1-dimensional space needs up to: 2 colors.

A 2-dimensional space needs up to: 4 colors.

A 3-dimensional space needs up to: ∞ colors.

I can easily picture why a 3D space has no limit to the number of colors (personally I always imagine color blocks hanging in space connected to every other color block by bendable wires), but I don't quite understand why the pattern is that way.

[Halfwhit]

Imagine the colours of a hypercube in 4-dimensional space!

[genewitch]

A mantis shrimp told me, quote, "it's alright, i guess, if you're in to that sort of thing"