In my previous posts I explained *lower* bounds for the Hadwiger-Nelson problem: we know that the chromatic number of the plane is *at least* 5 because there exist unit distance graphs which we know need at least 5 colors. Someday, perhaps someone will succeed in constructing an even bigger unit distance graph that requires 6 colors, and then we’ll know CNP .

But what about an *upper* bound? Can we say for sure that the CNP has to be *smaller* than some limit? Indeed, we can: we know that CNP . Today I want to explain how we can show that CNP ; in another post I’ll show the proof that CNP .

Proving an upper bound for the chromatic number of the plane is very different than proving a lower bound. A lower bound is all about showing that you *can’t* color the plane with a certain number of colors. An upper bound, on the other hand, is all about showing that you *can*. We know that CNP because there is a specific, valid way to color the plane using only seven colors! It *might* be possible to do it with fewer colors, using a very clever pattern, which is why is only an upper bound. But at least we know it can be done with .

Let’s start with something simpler. Imagine coloring the whole plane with a repeating pattern like this:

Can this be a valid coloring of the plane? (Of course, we already know it can’t because it only uses four colors, and CNP > 4; but let’s see if we can give a more direct argument why this is not valid). First of all, the squares can’t be too big: we don’t want any pair of points inside the same square to be 1 unit apart. This means the *diagonal* of each square has to be less than 1.

So if the diagonals of the squares are less than 1, the sides of the squares have to be less than . But the problem is that squares of the same color also have to be far enough apart so that no two points in same-colored squares are 1 unit apart. But in this scenario same-colored squares are separated by only one other square; if the sides of the squares is then they are too close.

This idea can be easily salvaged, however: we just need more colors!

Now we are using nine colors, with a repeating pattern instead of . Let’s see if we can make this work. Once again, the squares can’t be too big (lest two points inside the same square can be 1 unit apart) but same-color squares can’t be too close (lest two points in different same-color squares can be 1 unit apart). Call the side length of the squares. The first condition once again gives us . What about the second condition? The shortest distance between two same-colored squares is now , if you travel straight east-west or north-south. (You can confirm for yourself that any other line between same-colored squares is longer.) So we must have .

Can we pick a value of that makes and both true? Yes! Rearranging a bit, this just says . Since this gives us a valid range of values for ; any such value for gives us a valid -coloring of the plane.

Hence, it is possible to color the plane using 9 colors, such that no two points at distance 1 from each other have the same color! We don’t know if this is the *best* way to color the plane (in fact, it isn’t!), but at least we know it is *a* way. So this shows that CNP .

In my next post I’ll explain how we know that CNP : the proof is similar in spirit, but more complex (and, of course, more efficient) due to its use of hexagons instead of squares.