# Spatial dimension of a finite graph

If $$(X,d)$$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $$G(X,d)$$ given by $$V(G(X,d)) = X$$ and $$E(G(X,d)) = \big\{\{x,y\}:x\neq y\in X \text{ and } d(x,y)\leq 1\big\}.$$

As MO user @YCor pointed out in a comment to a recent deleted question, given any (not necessarily finite) simple, undirected graph $$G=(V,E)$$, the map $$d:V\times V\to \mathbb{R}$$ given by $$d(v,v) = 0$$ for $$v\in V$$, $$d(v,w)=1$$ iff $$\{v,w\}\in E$$ and $$d(v,w) = 2$$ otherwise gives a metric on $$V$$ such that $$G\cong G(V,d)$$.

If $$G=(V,E)$$ is a finite graph we define its spatial dimension $$\text{dim}_s(G)$$ to be the smallest non-negative integer $$n$$ such that there is $$S\subseteq\mathbb{R}^n$$ with $$G \cong G(S,||\cdot||)$$, where $$||\cdot||$$ denotes the Euclidean metric that $$S$$ inherits from $$\mathbb{R}^n$$.

Question. Given any integer $$n\geq 1$$, what is an example of a finite graph $$G=(V,E)$$ with $$\text{dim}_s(G)=n$$?

If $$s$$ obeys $$k_{n-1}, where $$k_n$$ is the kissing number of $$n$$-dimensional Euclidean space, then the star $$K_{1,s}$$ has dimension at least $$n$$. For instance, $$K_{1,7}$$ has dimension 3.
(In most cases where $$s\le k_n$$, $$K_{1,s}$$ has dimension exactly $$n$$, but there are exceptions. For instance $$K_{1,6}$$ has dimension 3, even though $$6\le k_2$$, because it turns out not to be possible for six unit disks in the plane to all touch a central disk without touching each other.)
• So is it possible for every $n\in\mathbb{N}$ to find a graph with spatial dimension exactly $n$? (Sorry if I am a bit slow in understanding whether your answer implies this.) – Dominic van der Zypen Dec 10 '18 at 13:49
• It seems very likely that this construction (with $s=k_{n-1}+1$) generates a graph with dimension exactly $n$, but it would require a proof that the graph $K_{1,s}$ can actually be embedded without extra ball intersections into $n$-dimensional space. There should be plenty of room to achieve this but I don't see how to prove it in generality. – David Eppstein Dec 10 '18 at 19:59