Color the plane so that no two points of the same color are at distance 1 apart. How many colors are needed? If instead, 3D space is colored, how many colors are needed there? Both are unsolved problems! The chromatic number of the plane is 4, 5, 6, or 7. This question is known as the Hadwiger–Nelson problem. In space, the range of possible values is 6–15.[more]
This Demonstration uses objects (known as spindles) that determine the lower bounds of these ranges. Drop an equilateral triangle with unit edges onto the plane. The three points are pairwise at distance 1 apart, so the plane requires at least three colors. Is there a larger graph that forces a 4-coloring? Two are shown here, the Moser spindle and the Golomb graph. One difficulty in finding these is that two unit circles can only intersect at two points. Any graph containing (four connected points) or (two points connected to three points) cannot be a part of a planar spindle.
For 3D space, a tetrahedron proves at least four colors are needed. Three 3D spindles forcing a 5-coloring are given. Two were found by Raiskii and Nechushtan. In  a method for combining these two spindles into a graph of around 400 vertices is given, which proves that space needs six colors. The third 3D spindle was found by the author. A cluster of 4 tetrahedra each sharing an edge looks like a PacÃ¢ÂÂMan. The double PacÃ¢ÂÂMan uses two of those.
The chromatic polynomial of each graph is calculated to find the number of colorings for each spindle.[less]
 Wikipedia. "Hadwiger–Nelson Problem." (Oct 22, 2015) en.wikipedia.org/wiki/Hadwiger% E2 %80 %93 Nelson_problem.
 D. Coulson, "A 15-Colouring of 3-Space Omitting Distance One," Discrete Mathematics, 256(1–2), 2002 pp. 83–90. doi:10.1016/S0012-365X(01)00183-2.
 O. Nechushtan, "On the Space Chromatic Number," Discrete Mathematics, 256(1–2), 2002 pp. 499–507. doi:10.1016/S0012-365X(00)00406-4.
Wolfram Demonstrations Project
Published: October 26 2015