Erdős [Er71] writes it is 'not difficult to see' that $C_\epsilon\to \infty$ as $\epsilon\to 0$.

This was solved in the affirmative by Kostochka and Pyber [KoPy88], who proved that $G$ must contain a subdivision of $K_5$ (which is non-planar) with $O_\epsilon(1)$ many vertices.

View the LaTeX source

A saturated planar graph on $3$ vertices is a triangle, which by Turán's theorem is contained in every graph on $n$ vertices with $\lfloor n^2/4\rfloor+1$ edges. Erdős [Er71] writes it is 'easy to construct' a graph on $n$ vertices with $\lfloor n^2/4\rfloor+\lfloor\frac{n-1}{2}\rfloor$ edges which contains no saturated planar graph with $>3$ vertices.

Erdős [Er69c] proved that every graph with $n$ vertices and $\lfloor n^2/4\rfloor+k$ edges contains a saturated planar graph on $\gg k/n$ vertices, answering a question of Dirac.

This was proved in the affirmative by Simonovits in his PhD thesis - indeed, it must contain either a $K_4$ or $C_l+2K_1$ for some $l\geq 3$. The proof is given by Cambie in the comments.

View the LaTeX source

This page was last edited 08 December 2025.

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.

View the LaTeX source

This page was last edited 02 October 2025.