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