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 able to prove till now...Now I think it is not true in general...I've an intuitive guess for a counter-example which is ...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.

So can any-body 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.

  • $\begingroup$ Would it be possible for you to provide an illustrative example? $\endgroup$ Aug 13, 2015 at 14:18
  • 1
    $\begingroup$ I am confused by your counterexample: Your set $X$ is just the set of squares of integers, and the distance is the usual distance. So, unless you mean something else by "graph" than what I understand by it, it seems like a non-counter-example. $\endgroup$
    – Igor Rivin
    Aug 13, 2015 at 14:24
  • 3
    $\begingroup$ Well, actually, yes, that is what I had meant, although the need for this is lessened now that Igor has pointed out that your proposed counterexample works trivially. As the comments show, at least some of us had misunderstood your question at first. An insightful example (not just any example) would have clarified things. In a general forum like this one, with mathematicians coming from diverse backgrounds, my opinion is that a mathematician can communicate more effectively with full and even redundant insightful explanations. $\endgroup$ Aug 13, 2015 at 15:31
  • 1
    $\begingroup$ @JoelDavidHamkins thank you for your advice...I'll be more careful as well as try to stay more clear about my questions and answers from next time...again thanks for your advice $\endgroup$ Aug 13, 2015 at 16:55
  • 2
    $\begingroup$ @Anubhav.K I know, but you started your question: "I've proved that ... " which gave me the intuition that you may not know the book of Bridson and Haefliger, which is really a great source for "statemants in this direction". That's why it was only a quick comment. Sorry if I'm mistaken :) $\endgroup$
    – M.U.
    Aug 13, 2015 at 23:01

2 Answers 2


If a graph is something where all edge lengths are $1,$ then your counter-example is fine. Take any (countable, for simplicity) set of points $X$, let $d_i$ be the distance from $x_i$ to its nearest neighbor. If $\lim_{i\rightarrow \infty} = \infty,$ then $X$ is not quasi-isometric to a graph. If it were, then the distance from $x_i$ to the closest neighbor would be $O(1).$ But it is not.


some more good answers of this question has been posted here (https://math.stackexchange.com/questions/1394463/is-every-metric-space-quasi-isometric-to-a-graph/1407173#1407173 )...

I think those answers could be helpful for others... I don't want any credit for this.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .