Problem 1007

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$ ?

Source: erdosproblems.com/1007

Graph theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

SOLVED (LEAN). The smallest number of edges is $9$ , attained only by $K_{3,3}$ among graphs without isolated vertices. The refereed source is Theorem 6 (Chaffee and Noble 2016) of Chaffee and Noble (Australas. J. Combin. 64 (2016), no. 2, 327--333; a refereed open-access journal): "The minimum number of edges of a graph $G$ with $\dim(G)=4$ is nine", with Lemma 3 (Chaffee and Noble 2016) ( $\dim(K_{n,m})=4$ for $m,n\ge3$ , taken from p. 119 of Erdős, Harary and Tutte, [EHT65]) supplying the nine-edge witness $K_{3,3}$ and Theorem 7 (Chaffee and Noble 2016) the uniqueness. The first proof is House's (Discrete Math. 313 (2013), 1783--1789; in the publisher's open archive): its main result (unnumbered; pp. 1783 and 1789) states that "the minimum number of edges which a 4-dimensional graph can have is 9, and there is only one such graph, namely $K_{3,3}$ ", as the 2016 paper's introduction reports it ("R. F. House showed that the answer to the above question is 9 and furthermore, that the complete bipartite graph $K_{3,3}$ is the unique graph that achieves this bound"). The 2016 paper's Theorems 10 and 11 give the dimension-5 value $15$ , attained by $K_6$ and $K_{1,3,3}$ , which the site records as context. The claim pages House 2013 and Chaffee and Noble 2016 record the two results, their postings and the acceptance evidence; the Lean development of 2026 described under Formalization declares itself a formalization of their result and is a formalization link on both pages, not a claim of its own; a second development of September 2026 formalizes the uniqueness theorem alone and is a formalization link on the Chaffee--Noble page. The standing in the frontmatter is derived from the two pages.

ChNo16: Chaffee, Joe and Noble, Matt, Dimension 4 and dimension 5 graphs with minimum edge set. Australas. J. Combin. 64 (2016), no. 2, 327--333 (received 14 January 2015, revised 19 July and 27 October 2015; the journal's volume listing carries the article,). Library home: Chaffee and Noble 2016. Lemma 3 and Theorem 6, p. 328; Theorem 7, p. 329; Theorems 10 and 11, pp. 330--331.
Ho13: House, Roger F., A 4-dimensional graph has at least 9 edges. Discrete Math. 313 (2013), no. 18, 1783--1789, doi:10.1016/j.disc.2013.05.005 (a Note; received 12 November 2012, accepted 9 May 2013, available online 4 June 2013, per p. 1783; Crossref record; published September 2013; the record carries the publisher's open-access user license dated 28 September 2017, the open archive). Definition 1, Problem 2 and the answer, p. 1783; Proposition 9 and the 43 candidate graphs, p. 1786; the closing statement, p. 1789 (in the publisher's open archive). Library home: House 2013.
So09e: Soifer, Alexander, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, New York (2009), xxx+607 pp., ISBN 978-0-387-74640-1, doi:10.1007/978-0-387-74642-5 (the site's reference text (2026-09-18) and the Crossref record). The site's only source key; [ChNo16] cites its pp. 88--93 as the place where Soifer "relates the following problem posed by Erdős in private communication". A book, not held.
EHT65: Erdős, P., Harary, F. and Tutte, W. T., On the dimension of a graph. Mathematika 12 (1965), 118--122, doi:10.1112/S0025579300005222 (received 7 January 1965, per p. 122). Not cited by the site; the source [ChNo16] names for its Lemmas 1--4 and, with [So09e] (pp. 88--93), [Ho13] names for its Proposition 3; it prints the definition and the values of Lemmas 1--3 but nowhere states the monotonicity of Lemma 4 (immediate from the definition). The definition and the values $\dim K_n=n-1$ and $\dim(K_n-x)=n-2$ , p. 118; the values of $\dim K_{m,n}$ , with Lenz's construction for $\dim K_{m,n}\le4$ , p. 119; the §1 values are unnumbered and asserted without printed proof except the construction. Theorem 1 ( $\dim G\le2\chi(G)$ ), p. 121, §2. Library home: Erdős, Harary and Tutte 1965.
ChNo17: Chaffee, J. and Noble, M., A dimension 6 graph with minimum edge-set. Graphs and Combinatorics (2017), doi:10.1007/s00373-017-1854-8. A citing paper found by title (the next dimension); title and record only; not held.

Problem 1007

Status

Proof claims

Discussion