Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

If $G$ is 2 - self centered graph. then how to prove that $G$ has at least $2n - 5$ edges? where $n\geq 5$.

I started by assuming if number of edges $\mid E\mid\leq 2n-6$ then there exist a vertex say $u$ such that $deg = 2$ otherwise if no such vertex exists then

$\mid E\mid\geq \frac{3n}{2}>2n-5$ (I am stucked here. How to prove this. Sincerely thanks for giving me time.)

share|cite|improve this question
Also posted to, where it ought to be closed sometime soon. So: what's a 2-self centered graph? – Gerry Myerson May 15 '12 at 6:01
It probably means a self-centered graph (diameter=radius) of radius 2. – hardmath May 15 '12 at 10:32
Since there are 2-self-centered graphs of arbitrarily large n, you will not be able to prove $\frac{3n}{2} \gt 2n-5$. – hardmath May 16 '12 at 17:14

I take it $n$ is the number of vertices. You might be interested in Among the things you'll find there is a link to a complete list of all self-centered graphs with diameter 2 that have minimum number of edges, and a link to a survey paper by Fred Buckley.

share|cite|improve this answer

i strongly recommend you to refere the following paper: Akiyama. j., Ando.K and Davis.D., Miscellaneous properties of equi eccentric graph in Convexity and Graph Theory. Proc. Conf. in Haifa Isreal-1981.

share|cite|improve this answer
Would you explain why this paper is useful for the Question? Answers are generally expected to address the Question being asked. – hardmath May 15 '12 at 10:43

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.