Suppose $\Gamma(V, E)$ is a graph, and $(M, \rho)$ is a metric space. Let's call a function $h: V \to M$ distance-embedding if it satisfies the property "$(v, u) \in E$ iff $\rho(h(v), h(u))=1$". Let's call $\Gamma(V, E)$ distance-embeddable in $(M, \rho)$, if one can construct a distance-embedding for it.
My question is:
What is the minimal number $m(n)$ of vertices a graph not distance-embeddable in $(\mathbb{R}^n, l_2)$ can have?
According to the "The realization of distances within sets in Euclidean space" by Larman and Rogers the chromatic number of any graph distance embeddable in $(\mathbb{R}^n, l_q)$ (for some arbitrary $q \geq 1$) does not exceed $(3+o(1))^n$. Thus, $m(n) \leq (3+o(1))^n$ with the example being a complete graph.
However, I do not know, how to get any better bounds...