# Show that the given two paths do not contain a common vertex, except one.

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.

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$$.

• 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? Feb 9, 2019 at 6:37
• Are you still here, monalisa? Feb 10, 2019 at 11:27
• @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$\$ Feb 10, 2019 at 12:28
• 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? Feb 11, 2019 at 4:37
• @GregMartin Yeah. I am adding to some specific procedure. Feb 11, 2019 at 4:42

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. Thus $$d(y,x_r)\leq r-1$$, a contradiction. Similarly, if $$x_j = x_r$$ then $$d(y,x_r) = i , again a contradiction.

Next let $$i\neq 1$$ and $$j\neq r$$. Since $$i, 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$$.