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