<p>This is not possible in general.</p>
<p>The 4-cycle is actually helpful to consider: embedding it in <span class="math-container">$\mathbb{R}^k$</span> in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be <span class="math-container">$1$</span> and those between the non-adjacent pairs must be <span class="math-container">$\sqrt{2}$</span>).</p>
<p>Now consider the complete bipartite graph <span class="math-container">$K_{2,3}$</span>. Let us call its vertices <span class="math-container">$a_1,a_2,b_1,b_2,b_3$</span>. In any embedding <span class="math-container">$f$</span> satisfying your condition, the 4-cycles <span class="math-container">$(a_1,b_1,a_2,b_2)$</span>, <span class="math-container">$(a_1,b_1,a_2,b_3)$</span> and <span class="math-container">$(a_1,b_2,a_2,b_3)$</span> would all have to be mapped to squares as above, but the first two of these conditions imply <span class="math-container">$f(b_2) = f(b_3)$</span>, contradiction.</p>

CC BY-SA 4.0
2020-08-20T14:23:26.803Z
Thanks a lot Klaus.
Andrea
CC BY-SA 4.0
2020-08-19T18:53:03.793Z
2020-08-19T18:53:03.793Z
Klaus Draeger
<p>Given an undirected and unweighted graph <span class="math-container">$G = (V, E)$</span>, is it possible to find a mapping <span class="math-container">$f: V \rightarrow \mathbb{R}^k$</span> for some <span class="math-container">$k$</span> such that for every <span class="math-container">$i, j \in V$</span>, <span class="math-container">$\|f(i) - f(j)\|_2^2 = \Delta(i, j)$</span>, where <span class="math-container">$\Delta(i, j)$</span> is the shortest path length between <span class="math-container">$i$</span> and <span class="math-container">$j$</span> in <span class="math-container">$G$</span>?</p>
<p>I have been testing a few counterexamples for which these isometric embeddings in <span class="math-container">$\ell_2$</span> fail to exist (for example, the 4-cycle), but in this case they work.</p>

CC BY-SA 4.0
2020-08-19T14:52:57.730Z
Notice that the standard metric over the Euclidean space is the $\ell_2$-norm $\|f(i)-f(j)\|_2$, rather than $\|f(i)-f(j)\|_2^2$. Any reason why you consider the squared $\ell_2$-norm?
smapers
CC BY-SA 4.0
2020-08-19T14:56:19.913Z
@smapers Because of the second paragraph?
Emil Jeřábek
CC BY-SA 4.0
2020-08-19T14:59:05.720Z
Oh, ofcourse, thanks!
smapers
CC BY-SA 4.0
2020-08-19T19:29:44.873Z
Metric embeddings is a well-explored topic. See book by Deza-Laurent https://www.springer.com/gp/book/9783540616115 or a web search will reveal several lecture notes and papers on this topic. Square distance embeddings are negative type metrics and one can in fact test, via semi-definite-programming, whether one can embed a given finite metric into a Euclidean space (no restriction on dimension). Many problems here are also NP-Hard.
Chandra Chekuri
CC BY-SA 4.0
2020-08-20T14:19:55.250Z
Thanks Chandra, the pointer turned out to be useful. I'm not an expert of the field and the only relevant theorem I was aware of is due to Schoenberg (https://www.ams.org/journals/tran/1938-044-03/S0002-9947-1938-1501980-0/S0002-9947-1938-1501980-0.pdf) but it is quite complicate to work with.
Andrea
<graph-theory><embeddings>
Isomorphic graph embeddings in the Euclidean Space
Andrea
# Isomorphic graph embeddings in the Euclidean Space

(Asked by: username_0 on 2020-08-19)

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|\_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path length between $i$ and $j$ in $G$?

I have been testing a few counterexamples for which these isometric embeddings in $\ell\_2$ fail to exist (for example, the 4-cycle), but in this case they work.

**Tags:** graph-theory, embeddings
> **Comments:**
> **username_1**: Notice that the standard metric over the Euclidean space is the $\ell_2$-norm $\|f(i)-f(j)\|_2$, rather than $\|f(i)-f(j)\|_2^2$. Any reason why you consider the squared $\ell_2$-norm?  
> **username_2**: @smapers Because of the second paragraph?  
> **username_1**: Oh, ofcourse, thanks!  
> **username_3**: Metric embeddings is a well-explored topic. See book by Deza-Laurent https://www.springer.com/gp/book/9783540616115 or a web search will reveal several lecture notes and papers on this topic. Square distance embeddings are negative type metrics and one can in fact test, via semi-definite-programming, whether one can embed a given finite metric into a Euclidean space (no restriction on dimension). Many problems here are also NP-Hard.  
> **username_0**: Thanks Chandra, the pointer turned out to be useful. I'm not an expert of the field and the only relevant theorem I was aware of is due to Schoenberg (https://www.ams.org/journals/tran/1938-044-03/S0002-9947-1938-1501980-0/S0002-9947-1938-1501980-0.pdf) but it is quite complicate to work with.  

---

## 1 answers

### Answer by username_4 on 2020-08-19. Score: 13 | Accepted answer

This is not possible in general.

The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $1$ and those between the non-adjacent pairs must be $\sqrt{2}$).

Now consider the complete bipartite graph $K\_{2,3}$. Let us call its vertices $a\_1,a\_2,b\_1,b\_2,b\_3$. In any embedding $f$ satisfying your condition, the 4-cycles $(a\_1,b\_1,a\_2,b\_2)$, $(a\_1,b\_1,a\_2,b\_3)$ and $(a\_1,b\_2,a\_2,b\_3)$ would all have to be mapped to squares as above, but the first two of these conditions imply $f(b\_2) = f(b\_3)$, contradiction.

> **Comments:**
> **username_0**: Thanks a lot Klaus.  

---

