Is every metric space quasi-isometric to a graph? I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$. During this proof I've precisely used the fact that given two point in $X$ there exists a distance minimizing curve inside $X$ joining those two points.
After this I've tried to generalize my proof for arbitrary metric space, which I could not. Now I think it is not true in general. I've an intuitive guess for a counter-example: consider $X=\{x_i \mid i \in \mathbb{N}\}$ and $d(x_i,x_j)= |i^2 - j^2|$. I think for this metric space there dose not exists any graph quasi-isometric with $(X,d)$ but till now I could not able to prove it.
Can anybody provide me some hints or some counter-example for this fact, or may be some proof of the fact that given any metric space there exists a graph quasi-isometric to that space?
 A: A metric space is QI to a connected graph iff it's large-scale geodesic. See Definition 3B1 here (my book with Pierre de la Harpe), and the characterization is an exercise (check the proof of Proposition 3B7(6)).
Large-scale geodesic implies large-scale connected, and your example (the set of squares of integers) is not even large-scale connected. 
A: The answer is negative. A metric graph $G$ is path-connected: any two points can be joined by a continuous path $\gamma:[0,1]\to G$. A quasi-isometry can destroy path-connectivity, but only to a point. Namely, if $f:G\to X$ is a quasi-isometry then the composition of a continuous curve $\gamma :[0,1]\to G$ with a quasi-isometry $f:G\to X$ is a function $g:[0,1]\to X$ that does not jump by more than $B$; that is, its pointwise oscillation, defined as 
$$\omega_g(x) = \limsup_{y\to x} |g(y)-g(x)| $$
is at most $B$ for every $x$. One may call such functions $B$-roughly-continuous.
Your example, $\{n^2 : n\in\mathbb{N}\}$, can be used here. Pick $n$ such that $(n+1)^2-n^2 > B$, and argue that there is no $B$-roughly continuous function from $[0,1]$ to $X$ that takes on the values $n^2$ and $(n+1)^2$. Indeed, for such a function both sets $\{t:g(t)\le n^2\}$ and $\{t:g(t)\ge (n+1)^2\}$ would be nonempty, disjoint, and open in $[0,1]$.
(For example: if $g(t)\le n^2$, then $t$ has a neighborhood in which $g<n^2+B+\epsilon$, but this means $g\le n^2$ in this neighborhood if $\epsilon$ is small enough.)
