Erdős #1066 · graph theory / planar graphs

Such graphs are always planar. Erdős initially thought that $g(n)=n/3$, but Chung and Graham, and independently Pach, gave a construction that shows $g(n)\leq \frac{6}{19}n$. Pach and Toth [PaTo96] improved this to $g(n)\leq \frac{5}{16}n$.

Pollack [Po85] noted that the Four colour theorem implies $g(n)\geq n/4$, since the graph is planar. Pollack reports that Pach observed that this in for unit distance graphs the four colour theorem can be proved by a simple induction.

This lower bound has been improved to $\frac{9}{35}n$ by Csizmadia [Cs98] and then $\frac{8}{31}n$ by Swanepoel [Sw02]. The current record bounds are therefore

Pollack [Po85] also reports a letter from Erdős which poses the more general problem of, given $n$ points in $\mathbb{R}^d$ with minimum distance $1$, let $g_d(n)$ be maximal such that there always exist at least $g_d(n)$ many points which have minimum distance $>1$. Is it true that $g_d(n) \gg n/d$ in general? The upper bound $g_d(n) \ll n/d$ is trivial, considering widely spaced unit simplices.

See [1070] for the general estimate of independence number of unit distance graphs.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.