Like many, I have been done a lot of reading of the Four Colour Theorem and there is one question that is vexing me to the point where I am sure I am misunderstanding. I hope that someone could help me out.
The established proof uses Euclidian mathematics to find a minimum state and then using computer power to check an extremely large number of cases. The consensus seems to be that there is no proof that doesn't require a computer. I have read one or two that claim to be able to:(https://arxiv.org/pdf/1701.03511.pdf) (http://www.dharwadker.org/proof.pdf) However I haven't tested them.
My point is that current proofs all create a connected, planar graph and then look at finding their minimum. But couldn't you just find the maximum connected planar graph (i.e. K4)? In other words, couldn't you just prove that the most number of countries that you can have where every country is touching every other one is 4? Basically saying that this is the worst-case scenario, so 4 is the most number of colours you would need. The maths is well established (Brooks' Theory etc.) and this wouldn't require any computational processing at all.
Is this what people are doing already and I'm just not understanding? My thinking goes like this:
Two adjacent vertices each with a different colour. If you add a third but it’s adjacent to just one, then you don’t need a third colour; only if it is adjacent to both. Similarly you only need a fourth colour if four vertices are all adjacent to each other. 5 vertices is not planar, so the highest possible configuration is with 4 countries. Therefore you can colour any map with 4 colours or less.
I am confident that any vertex can be considered by these terms through it’s relationship with the vertices adjacent to it, regardless of what those vertices are in turn adjacent to.
It's true that no planar graph can have $5$ vertices that are all adjacent to each other, but that's not the only way for $5$ colors to be necessary.
For example, the following graph doesn't contain $4$ vertices all adjacent to each other:
It only contains triangles, which force us to use $3$ colors, and in fact if you start coloring the graph, you'll be able to use $3$ colors for most of it. For example, you might color the center vertex red, and then alternate blue and green around the outside cycle...
...but then as you're about to finish the cycle, the last vertex already has a red, blue, and green neighbor. You're forced to use a fourth color.
This is also why the four-color theorem is hard to prove. We know that no $5$ vertices of a planar graph can all be adjacent, so we can color any $5$ vertices with $4$ colors, and keep coloring for a while. But we don't know, without lots of effort, that we won't get stuck at the end for some other reason.
(In fact, abandoning planar graphs for a moment, the Mycielski graphs are a sequence of graphs that don't even contain triangles ($3$ vertices, all adjacent) but require more and more colors to color: the $k^{\text{th}}$ Mycielski graph has chromatic number $k$. So any proof of the four-color theorem has to use some other property of planar graphs that's not true of the Mycielski graphs.)