It is a famous open problem to determine the chromatic number of the graph $G=G(\mathbb{E}^2,\{1\})$ whose vertices are the point in the plane and two vertices are linked by an edge when they are at Euclidean distance $1$ one from the other. This number is known to be between $4$ and $7$.

It is a theorem of De Bruijn and Erdös that the axiom of choice implies that the chromatic number of a graph is the maximal chromatic number of its finite subgraphs. As the axiom of choice does matter in certain such coloring problem, it is worth considering the following as a slight variant of the above question: what is the maximal chromatic number of a finite subgraph of $G$?

Since this question is obviously too difficult, let us ask about a stronger statistic: what is the maximal minimum degree of finite subgraphs of $G$? Recall that the chromatic number of a graph is at most its degeneracy plus one, where degeneracy is the least number $k$ such that inductively pruning the vertices of degree at most $k$ empties the graph.

I expect this question to be open, and my real question is (at last) the following:

What is the maximal minimum degree of known finite subgraphs of $G$?

I ask it because most unit-distance graphs I saw have a vertex of degree $3$. If this where true for all finite subgraphs of $G$, then it would have chromatic number $4$; but there are $4$-regular finite subgraphs of $G$. Does anyone knows how to achieve $5$?


For arbitrary $m$ there is an $m$-regular unit-distance graph isomorphic as a graph to an $m$-cube (of course these all have chromatic number $2$): Suppose you have a unit graph isomorphic to a $k$-cube ( so $2^k$ vertices and regular of degree $k$ with a total of $k$ slopes for edges.) To get one isomorphic to a $k+1$ cube, just imagine two copies right on top of each other and translate one of them a distance of $1$ in some direction not parallel to one of the $k$ current directions. It is possible, if desired, to have all the points rational with a not too bad common denominator using the method in the solution by Butch Malahide.

More generally, suppose you have unit graphs with $v_1$ and $v_2$ vertices regular of degrees $d_1$ and $d_2$ (or merely having those minimum degrees). Then the $v_1v_2$ points obtained by adding one point from each make a unit distance graph regular of degree $d_1+d_2$ (or having that minimum degree). You might need to rotate one graph to avoid coincidences. This is called the cartesian product of the two graphs. One unfortunate property (for us) is that the chromatic number of the product graph is just the maximum of the chromatic numbers of the two "factor" graphs.

So there should be a $6$-regular $27$ point unit distance graph and a $7$-regular $54$ point graph. However these all have chromatic number $3$. Is this the least possible number of vertices for a unit distance graph with minimum degree $7$?

  • $\begingroup$ I chose this solution as it is so simple that reading the first line made me feel like a fool. Thanks also to Butch Malahide, my question was really naive. $\endgroup$ – Benoît Kloeckner Jun 5 '13 at 8:08

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.