Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$

Question

Question:

is it always possible to embed a complete, symmetric and metric graph $G$ with $n+1$ vertices isometrically in $\mathbb{R}^n$?

I'm convinced it must be true, but can't remember having seen a proof of it.

Addendum:
The following is a simple counterexample for $n=3$:
take as the vertices the corners of a planar strictly convex quadrilateral and as edgelengths the euclidean distance between the points they connect.
If the weight of an edge that corresponds to a diagonal is increased the resulting $K_4$ can't be embedded isometrically in $\mathbb{R}^3$, the reason being that the other diagonal "acts" as a hinge joint and rotating the adjacent triangles around it, out of the planar position, inevitably brings their opposite corners closer together.

Answer 1

With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. The required embedding $f$ is easy to define. Label the $n$ points as $x_0, x_1, \dots, x_{n-1}$ and let $d(i,j)$ denote the distance between $x_i$ and $x_j$. Let $f(x_0)$ be the zero vector in $\mathbb{R}^{n-1}$ and for all $i,j \in [n-1]$, let $f(x_i)_j=d(i,j)-d(0,j)$. It is easy to check that $\|f(x_i) - f(x_j)\|_\infty=d(i,j)$ for all $i,j \in \{0, \dots, n-1\}$.

However, for other $\ell_p$-norms this is false. Ball proved that for all $n \geq 3$, there are $n$-point $\ell_1$-spaces that require dimension at least $\binom{n-2}{2}$ to embed in $\ell_1$. Ball also proved that for all $1 < p < 2$ and $n \geq 3$, there are $n$-point $\ell_p$-spaces that require dimension at least $\binom{n-1}{2}$ to embed in $\ell_p$. Of course, it is also well-known that there are $n$-point metric spaces that are not embeddable in $\ell_2$ (no matter what the dimension). For the references (and other related results), see the introduction of my paper The excluded minors for isometric realizability in the plane with Samuel Fiorini, Gwenaël Joret, and Antonios Varvitsiotis.

Answer 2

For an isometric embedding the distances in the graph must satisfy at least the triangle inequality. Let me assume that this is implicit in your notion of "metric graph". But then with more than three vertices, the distances in the graph must also have a non-negative Cayley-Menger determinant, which is stronger than satisfying a triangle inequality for each 3-cycle. So there are 4-vertex graphs that do not embed isometrically in any Euclidean space. And this is the only obstruction: as soon as your $K_{n+1}$ has a non-negative Cayley-Menger determinant, it embeds isometrically into $\Bbb R^n$.