Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove the following..

If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same for its complement too. Any hint or suggestion will be helpful. Thanks for helping me.

share|cite|improve this question
Can you define what is ecentricity? Is it just the valency of each vertex? – Easy Apr 22 '13 at 12:22
@Easy sir.... eccentricity of a vertex v is defined as the greatest distance between v and any other vertex of the graph. That is, e(v) is the distance between v and a vertex farthest from v – monalisa Apr 22 '13 at 12:29
up vote 3 down vote accepted

Fix a vertex $v$. Suppose $u$ the vertex that has the greatest distance from $v$. Then an isomorphism $\varphi$ maps $u,v$ to $\varphi(u),\varphi(v)$ and preserves their distance. Assume for the vertex $\varphi(v)$, there exists a vertex $w$ has longer distance than $\varphi(u)$. Then $d(v,\varphi^{-1}(w))>d(v,u)$, a contradiction.

For the complement, simply notice that it is also vertex-transitive.

share|cite|improve this answer
Sir i got that complement will be also vertex transitive. But can you explain briefly how we get that the eccentricity will be same for all vertices in a transitive graphs. Thanks – monalisa Apr 22 '13 at 12:36

Hint: First prove that a graph isomorphism preserves distances, and therefore also eccentricities.

share|cite|improve this answer
thanks sir, but can you please elaborate it more. about eccentricities specially. – monalisa Apr 22 '13 at 12:38
Not without handing you the entire solution, I'm afraid. And don't sir me! – Henning Makholm Apr 22 '13 at 12:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.