I was trying to prove some result and I am stuck at the following thing.

Given a graph $G$ of diameter two, $d(x,y) = 2$, where $x$ and $y$ are in $G$ and we add $r-1$ vertices $u_1,\ldots,u_{r-1}$ to obtain a path $P : x-z-y-u_1-u_2-\ldots- u_{r-1} $ of length $r+1$. Similarly, we add $r$ vertices to obtain a path $Q: y-x_1-x_2-\ldots- x_r $ of length $r$. Now I have to show these two paths can not have a common vertex except $y$.

I have an intuition that if they have some common vertex other than $y$ then the length of one path will be altered. But how to prove this. Can anyone suggest me some ideas or hints to prove this.

Added details:

In the above problem, we have assumed that eccentricity of $x$ and $u_{r-1}$ is $r+1$, and hence $d(x,u_{r-1})=r+1$, while rest of the vertices have eccentricity $r$. I am trying for some construction, where I need to show that we need at least $2r-3$ new vertices to be added. So, path $P$ gives $r-1$ vertices, and path $q$ at least contains $r-2$ vertices. Thus, total at least $2r-3$ vertices. That detail has been proved. I just need one more point to prove. That these two paths can not share any other vertex other than $y$.

  • $\begingroup$ Suppose $u_i=x_j$. See how this gives you a new path from $x$ to $u_{r-1}$? and a new path from $y$ to $x_r$? How long are those new paths? $\endgroup$ Feb 9, 2019 at 6:37
  • $\begingroup$ Are you still here, monalisa? $\endgroup$ Feb 10, 2019 at 11:27
  • $\begingroup$ @GerryMyerson Yeah sir. I am trying. I am getting so many conditions too. Like it depends if $i<j$ or $i>j$? or what could happen if I take $|i-j|=2$$ $\endgroup$
    – monalisa
    Feb 10, 2019 at 12:28
  • $\begingroup$ In the generality you've stated it, I see no reason why the two paths couldn't intersect each other. Are you adding vertices according to some specific procedure, or just arbitrarily? $\endgroup$ Feb 11, 2019 at 4:37
  • $\begingroup$ @GregMartin Yeah. I am adding to some specific procedure. $\endgroup$
    – monalisa
    Feb 11, 2019 at 4:42

1 Answer 1


Kindly let me know if I did the right thing here.


We have three different cases here.

Case 1. Let $i = j$.

In this case, the distance between $y$ and $x_r$; $x$ and $u_{r-1}$ remains the same. However, we obtain a $x$--$x_r$ path $x-z-y-u_1-u_2-\ldots-u_i=x_j-x_{j+1}-\ldots-x_r$, where $l(p) = r+2$, which is a contradiction because $e(x) = r+1$. \

Case 2. Let $i < j$.

If $u_i = u_1$ then we get a path $y-u_1=x_j-x_{j+1}-\ldots-x_r$ of length $r+1-j$. Since $i = 1$ and $j>i$, we have $r+1-j<r$. Thus $d(y,x_r)\leq r-1$, a contradiction. Similarly, if $x_j = x_r$ then $d(y,x_r) = i <r$, again a contradiction.

Next let $i\neq 1$ and $j\neq r$. Since $i<j$, we have $j-i\geq 1$. In this case, we obtain a $y-x-r$ path $P_1 : y-x_1-x_2-\ldots-x_i=u_j-u_{j+1}-\ldots-u_r$ of length $r-j+i = r- (j-i)$. Since $j-i\geq1$, $l(P_1)\leq r-1$, a contradiction as eccentricity of $y$ is $r$. \

Case 3. Let $i > j$ which gives $i-j\geq 1$.

Here, we obtain a $x-x_{r-1}$ path $Q:x-z-y-x_1-x_2-\ldots-x_i=u_j-u_{j+1}-\ldots-u_{r-1}$, where $l(Q) = r+ ( i-j)$. Now, as $i-j\geq 1$, we have $l(Q)\leq r$, which contradict the fact that eccentricity of $x$ is $r+1$.


You must log in to answer this question.

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