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$.
Best Answer
Kindly let me know if I did the right thing here.
UPDATED ANSWER
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$.