Problem #1066: Let $G$ be a graph given by $n$ points in $\mathbb{R}^2$,...

---

Progress

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\[\frac{8}{31}n \approx 0.258n \leq g(n) \leq 0.3125n=\frac{5}{16}n.\]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.