SOLVED
This has been resolved in some other way than a proof or disproof.
The dimension of a graph $G$ is the minimal $n$ such that $G$ can be embedded in $\mathbb{R}^n$ such that every edge of $G$ is a unit line segment.
What is the smallest number of edges in a graph with dimension $4$?
The notion of dimension of a graph was defined by Erdős, Harary, and Tutte. This was question was posed by Erdős to Soifer in January 1992.
The smallest number of edges is $9$, achieved solely by $K_{3,3}$, proved by House
[Ho13]. An alternative proof was given by Chaffee and Noble
[ChNo16], who also prove that the smallest number of edges in a graph of dimension $5$ is $15$ (achieved by $K_6$ and $K_{1,3,3}$).
View the LaTeX source
Additional thanks to: Boris Alexeev
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1007, https://www.erdosproblems.com/1007, accessed 2026-01-16
