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