When graph theory makes it to the news, you know there is a fun problem at its source. That is the case with a recent breakthrough by Aubrey de Grey who showed that you cannot color the plane with four colors. Here is the graph that he discovered that has chromatic number at least five.

Below, I’ll explain what this means and what was involved in the discovery.

How to color graphs

Colouring graphs is an old pastime for math enthusiasts and an active research topic in the graph theory community. A proper coloring of a graph is an assignment of labels to vertices, often numbers or colors, so that two adjacent vertices receive different labels. This notion is motivated by coloring maps, where you want neighboring countries to receive different colors.

The famous Four Color Theorem says that you can properly color any map with at most four colors. All known proofs of this theorem rely on checking cases with a computer.

The minimum number of colors you need to properly color a graph is its chromatic number. Coloring graphs is a hard problem in a precise sense: it is known to be an NP-complete problem when the number of colors is at least 3. In simple language, this means we are unlikely to find a “fast” algorithm that would determine if a graph can be properly with three or more colors.

Unit distance graphs

If we can draw a graph G in the plane so its edges have unit distance, then we call G a unit distance graph. Consider the graph I will call P, whose vertices are the points in the plane, and vertices are adjacent if they are Euclidean distance exactly one apart. For example, (0,0) and (0,1) are adjacent, while (0,0) and (1,1) are not. Observe that P is an infinite graph.

A natural question that emerges is to determine the chromatic number of the plane. This is called the Hadwiger-Nelson problem, and it dates back to the 1950’s.

The Moser spindle (below) is an example of a unit distance graph that has chromatic number four. For this reason, the chromatic number of P is at least four, as the Moser spindle is a subgraph of the infinite plane graph.

An explicit proper coloring of the plane is known with seven colors, so what this tells us that the chromatic number of P narrows down to one of the four values: 4, 5, 6 or 7.

Not Four

Aubrey de Grey discovered an example of a graph G with 1,581 vertices, which is a unit distance graph and has chromatic number larger than four. Hence, the chromatic number of P is either one of 5, 6, or 7.

His preprint is on arXiv:

Aubrey D.N.J. de Grey, The chromatic number of the plane is at least 5, Preprint 2018.

There are at least two things that make this result remarkable.

First, the Hadwiger-Nelson problem is simple to state and understand, even without a background in graph theory. If you review the proposed proof of de Grey, then you’ll notice that the author uses elementary notions in graph theory. That doesn’t mean the constructions found in the proof are obvious.

The main idea of the proof is to build up a sequence of increasingly complex graphs, and these can be used to build a unit distance graph G that has the desired property of having chromatic number larger than 4.  The graph G is an obstruction to the infinite plane graph having chromatic number 4. The proof, like the proof of the Four Color Theorem, is computer-assisted. Work on the joint computing project Polymath has reduced the size of the obstruction graph to 874 vertices.

Second, the scholar who discovered the proof is not a formally trained mathematician. Instead, he is best known for his works in the area of regenerative medicine and anti-aging. This is an exception to the rule for most mathematical discoveries, which are typically found by professional mathematicians. Mathematics is for everyone!

What is the exact value is the chromatic number of the plane? Is it 5, 6, or 7?  No one knows for sure, but we have one less value to worry about now thanks to this fantastic breakthrough.

Anthony Bonato