Proof strategy for 4-Colour-Theorem

Question

Suppose you have a triangulated region in the plane, the triangulation consisting of $n$ triangles. Take an arbitrary triangle of this triangulation and call it $\Delta_i$ with $1\leq i\leq n$.

The neighbourhood of $\Delta_i$, i.e. all the triangles around $\Delta_i$ which share a vertex or an edge with $\Delta_i$, we call this neighbourhood $N_i$.

If we can prove that you can label the vertices of $\Delta_i$ and its neighbourhood $N_i$ with just 4 colours, i.e. such that all adjacent vertices have different colour: does the 4-Colour-Theorem follow?

My thinking is: yes it follows, because $\Delta_i$ was arbitrarily chosen in this triangulation. Therefore we can conclude the whole triangulation can be 4-coloured. And if 4 colours suffice for an arbitrary triangulation, then 4 colours also suffice for any plane graph.

Would this be a valid proof strategy for the 4-Colour-Theorem, or am I taking the wrong conclusion?

Answer 1

If your proof strategy worked, it would prove too much.

Define a locally planar graph on a surface such as the torus to be a graph which looks like a planar graph within any "small region". (By "small", we can mean the neighborhood of a triangle, or more generally the subgraph within some fixed constant distance of any vertex). Then if your proof strategy worked, it would show that all locally planar graphs are 4-colorable as well.

However, there are counterexamples on other surfaces: for example, here is a counterexample on the torus, taken from Locally planar toroidal graphs are 5-colorable by Albertson and Stromquist. (Opposite sides of the rectangle in this diagram wrap around.)

It can be shown that in any 4-coloring of any triangulation on any surface, if there are only two vertices of odd degree, they must have the same color. However, in the example above, there are two such vertices, and they are adjacent: so this graph has no 4-coloring.

Nevertheless, we can pick any triangle within this graph, and 4-color that triangle and its neighborhood (by the 4-color theorem). It is the global properties of this graph that ultimately stop us. To take your argument, and turn it into a proof of the 4-color theorem, you would have to show that in a planar graph, there cannot be a global obstacle.

Answer 2

Note that the property you stated only refers to "local" properties of the triangulation. However, the 4-color theorem is a global property (i.e. involving all parts of the triangulation at the same time). So in general it is not a valid logical inference.

Indeed, the 4-color theorem depends in an essential way on (global) topological information of the plane. So if you replace the plane with, say, a torus, it becomes the 7-color theorem. However, if your argument were true then you would prove the 4-color theorem on tori also, which is absurd.

Answer 3

Trebor has already given an answer that more than suffices to show to that we shouldn't expect this method to work for map colouring, but it is worth pointing that similar difficulties arise even for general graph colouring.

The problems of colouring a graph optimally, and `extending' a colouring are quite different. I can have a graph $G$, with a subgraph $H$, and then find an optimal colouring of $H$ that cannot be extended to an optimal colouring of $G$. So by colouring $\Delta_i$ and its surrounds in what looks like an optimal way, you can inadvertently get stuck with something that cannot be part of a 4-colouring.

For a concrete example, in the picture below, we can colour $H$ optimally in 2 ways, one of which does not extend to an optimal colouring. Inside of $H$, there's no real way of telling apart these colourings.

Further, there is another difficulty. 4-Coloring a triangle and all its neighbors amounts to finding a 4-colouring of some arbitrary maximal planar graph of diameter 3 or less, which is still very, very difficult in general.

Answer 4

Your argument resembles a heuristic argument of another well-known historical case: can you bound the chromatic number of graphs with large girth (i.e. no short cycles)? If you consider graphs with no cycles shorter than, say, 1001, can you give an upper bound on the chromatic number? It's not unreasonable to think something like that might exist: if you take any 1000 vertices, they induce a forest, which is 2-colorable. As @bof says in a comment, your argument would try to say that such a graph would then be 2-colorable, since the vertices were chosen arbitrarily. For this to work though, you'd need to say something about how those patches of 1000 vertices, with their 2-colorings, can be made compatible with each other. And that kind of argument is sound and common in coloring proofs: color part(s) of the graph, and finagle things until you can extend the coloring.

(It seems reasonable to hope that in the high-girth case, you could wrangle colors to match up well enough, but Erdős famously used the probabilistic method to show that we cannot: there are (enormous) graphs with arbitrarily large girth and chromatic number.)