# Is every finite graph isomorphic to the proximity graph of some $S\subseteq \mathbb{R}^n$?

This is the question that I should have asked before asking this older question.

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)$$.

Question. If $$G=(V,E)$$ is a finite graph, is there a positive integer $$n\in\mathbb{N}$$ and a finite subset $$S\subseteq \mathbb{R}^n$$ such that $$G \cong G(S,||\cdot||),$$ where $$||\cdot||$$ denotes the Euclidean metric that $$S$$ inherits from $$\mathbb{R}^n$$?

Yes. If $$n=|V|$$, then for small $$\varepsilon$$ any metric spaces on $$n$$ points with distances belonging to $$\{1-\varepsilon, 1+\varepsilon\}$$ is embeddable to $$\mathbb{R}^{n-1}$$.
• Do you have a proof (or reference) for the existence of this small $\varepsilon$? – Dominic van der Zypen Dec 10 '18 at 8:33
• Both proof and reference. You start with a regular simplex $\{v_0,v_1,\dots,v_{n-1}\}$, with all distances equal to 1, and look for the points $u_i$ close to $v_i$ in the affine hull of $v_0,\dots,v_i$. The map which sends such a sequence of vertices to the array of mutual distances has non-zero Jacobian (easy to see in appropriate coordinates), thus the claim follows from inverse function theorem. Alternatively you may use explicit conditions on embeddability to $\mathbb{R}^d$ via positive definiteness, like Schoenberg. – Fedor Petrov Dec 10 '18 at 8:47