• Any graph $G$, $d(u,v)$ denote the length of the shortest path from $u$ to $v$.
  • $\epsilon (u) =$ max$_{v \in V(G)}d(u,v)$ is called eccentricity of $u$ and $r$ = min$\epsilon (u)$ denote the radius of a graph $G.$

  • Center of a graph $G$ is the set of all vertex $u$ such that $\epsilon (u) = r$.

Let $G$ be a triangle free graph. Then center of $G$ has atmost two vertices.

I want to show by contradiction. Suppose that the center of $G$ has atleast three vertex says $u,v,w$. Then there exist $x,y,z \in V(G)$ such that $\epsilon (u) = \epsilon (v) = \epsilon (w) = d(u,x) = d(v,y) = d(w,z)$. If $u$ is not adjacent with $v$, then $d(u,v) > d(u,x )$, which is a contradiction. Thus $u,v,w$ form a triangle which is a contradiction.

I think this is right. Please check this. Thanks in advance.

  • $\begingroup$ Not sure how you determined $d(u, v)>d(u, x)$. $\endgroup$ – Dark Logician Jul 26 '17 at 4:56
  • $\begingroup$ I feel that it should be right , but i do not know how to prove. $\endgroup$ – user120386 Jul 26 '17 at 5:17
  • 2
    $\begingroup$ If $G$ is a regular $n$-gon, isn't every vertex in the center by symmetry? $\endgroup$ – stewbasic Jul 26 '17 at 6:11
  • $\begingroup$ maybe there's something missing in the question, but the picture in the Wikipedia definition of the center of a graph gives a counterexample to that statement: en.wikipedia.org/wiki/Graph_center#/media/File:Graphcenter.svg $\endgroup$ – user96233 Jul 29 '17 at 20:07
  • $\begingroup$ This statement is used in some theorem.Thats why I had asked this question here. Thanks to all $\endgroup$ – user120386 Jul 31 '17 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.