4
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ The cycle graph $C_n$ is $2$-colourable only if $n$ is even. So $C_{1001}$ is not $2$-colourable. But every neighbourhood is $2$-colourable, even if you define your "neighbourhoods" to consist of $100$ consecutive vertices; you don't need the third colour unless you go all the way around. $\endgroup$
    – bof
    Aug 29 '20 at 16:10
  • $\begingroup$ @bof Wow thanks a lot - this is a compelling example! I see your point. It is a great counterexample to what I had in mind! Is there a "canonical" way how to draw conclusions from neighbourhoods in a graph for the whole graph? $\endgroup$ Aug 29 '20 at 16:14
5
$\begingroup$

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

Figure 7 from paper above: A locally planar graph with only two odd vertices, which are adjacent

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.

$\endgroup$
3
  • $\begingroup$ this is an excellent answer! It is very clear, and the example is great. Thank you also for the useful reference link! $\endgroup$ Aug 29 '20 at 17:41
  • $\begingroup$ one final question: if my starting point is a region in the plane with a boundary (i.e. not boundaryless like a torus), does my argument still break? I fear it still breaks, as illustrated by the example of bof in the comments and by Brandon du Preez $\endgroup$ Aug 29 '20 at 17:45
  • $\begingroup$ The problem is that your argument doesn't do anything that would distinguish a triangulation of a region in the plane with a boundary from a triangulation of a torus. The question is not whether it's possible to 4-color the planar triangulation (we already know that the 4-color theorem is true), but whether your argument proves that it's possible. For that, at some point, you'd have to use some property that the planar triangulation has, but the toroidal triangulation does not. $\endgroup$ Aug 29 '20 at 17:49
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you for your answer. Please let me know, what is missing in my argument? Because if all the neighbourhoods of $\Delta_i$ only need 4 colours, then the whole triangulation only needs 4 colours. Where does this argument "break"? - In other words, what exactly is the global topological information of the plane that interferes with my argument (or where is the gap in my argument relative to the global properties of the plane? $\endgroup$ Aug 29 '20 at 16:06
4
$\begingroup$

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.

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Very helpful example! Thank you for that. $\endgroup$ Aug 29 '20 at 16:17
  • $\begingroup$ Glad to be of help ^^ $\endgroup$ Aug 29 '20 at 16:18
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for this interesting extra perspective! Interesting link (or non-link) between girth and chromatic number! $\endgroup$ Sep 6 '20 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.