Dimension 4 and dimension 5 graphs with minimum edge set
Joe Chaffee, Matt Noble · Australas. J Comb. · 2016
The dimension of a graph G is defined to be the minimum n such that G has a representation as a unit-distance graph in R n . A problem posed by Paul Erd˝ os asks for the minimum number of edges in a graph of dimension 4. In a recent article, R. F. House showed that the answer to Erd˝ os’ question is 9. In this article, we give a shorter (and we feel more straightforward) proof of House’s result, and then extend our methods to answer the question for dimension 5 as well. It is ultimately shown that a dimension 5 graph has at least 15 edges, and that this lower bound is realized only by two graphs: K6 and K1,3,3.