# Uniquely 4-colorable Unit Distance Graphs

A graph is "unit distance" if it can be embedded in the plane in such a way that whenever two vertices are connected by an edge, their distance is $1$.

A graph is uniquely $4$-colorable if there is a unique way (up to renaming of colors) of coloring its vertices with $4$ colors in such a way that no two adjacent vertices have the same color, and if no such coloring with $3$ colors exists.

Question: Is there finite graph that is both uniquely $4$-colorable and unit distance?

• Complete graphs $K_n$ are examples for $n=1\ 2\ 3\$ (am I right?). Dec 13 '16 at 20:42
• @WłodzimierzHolsztyński No, at least 4 colors should be required. I have edited the question to make this clear. Dec 13 '16 at 22:47
• (Perhaps a phrase "with less than 4" should be more complete than "with 3"). Dec 14 '16 at 0:58
• Of course this question by now is obsolate since de Grey has found a 5-chromatic unit distance graph. Aug 3 '18 at 5:50

EDIT the original answer was wrong, thanks to Jan Kyncl for pointing the mistake, hopefully it is fixed now.

I think this is open, since existence will improve the lower bound of chromatic number for unit distance graphs from $4$ to $5$ almost surely.

Assume uniquely $4$ colorable finite unit distance graph $G$ exists. Color it with colors $a,b,c,d$. Take two copies of $G$: $G_1$ and $G_2$. For vertices colored $a$, $a_1 \in G_1, a_2 \in G_2$ merge $a_1$ and $a_2$ to vertex $A$ to get unit distance graph $G'$ with the property that all vertices in $G_1,G_2$ which are colored $a$ have the same color in all $4$ colorings of $G'$. For vertices $a_1' \in G_1, a_2' \in G_2$ colored with the $a$ color, rotate $G_2$ with center $A$ trying to get $a_1',a_2'$ at distance $1$. The triangle inequality is enough. If you can do this, add edge $(a_1',a_2')$ to get unit distance graph, which is not $4$ colorable. I think such four vertices exist with high probability and comment by Pat Devlin confirms this.

• This is in fact a complete proof of what you say (i.e., you could use it to show $\chi \geq 5$ for unit distance graph). Say $u$ and $v$ must be colored the same. Then make your two copies of $G$ and put vertices corresponding to $u$ in the same spot. Rotate until the vertices corresponding to $v$ have unit distance (ok by intermediate value theorem). $\qed$ Dec 14 '16 at 20:06
• In fact, this shows something stronger. We can add any edge to the (full) unit distance graph without changing its chromatic number. Dec 14 '16 at 20:11
• Why is $G'$ uniquely $4$-colorable? Can't you rename the three other colors in $G_2$ in five more ways? Dec 15 '16 at 0:32
• @JanKyncl Thanks, you are right. $G'$ is unit distance, but not uniquely 4 colorable. Looks like the main idea can be saved: In $G'$ all vertices which are colored $a$ in $G_1$ and $G_2$ are of the same color in all 4 colorings of $G'$, so the two new vertices must be colored $a$ in addition.
– joro
Dec 15 '16 at 6:02
• @PatDevlin Thanks. My original answer had error, edited. Another possibility is to take more copies of $G$, merge and rotate. Finally add an edge.
– joro
Dec 15 '16 at 6:53