Let $4\leq r\leq \lfloor\frac{n}{2}\rfloor$ and $P_n$ be a path graph on $n\geq 2r$ vertices.
$V(P_n) = \{v_1,\ldots,v_n\}$.
We obtain a graph $H$ by adding a vertex $x$ to $P_n$ such that $x$ is adjacent to vertices $v_l$ and $v_m$ such that $d(v_1,v_n) = r+1$, where $l<m$, $l\neq 1$ and $m\neq n$. $P_n$ induced graph in $H$. For other vertices in $H$, Eccentricity is $r$. Obviously, $v_2,\ldots,v_{l-1},v_{m+1},v_{n-1}$ can not be adjacent to $x$ otherwise $d(v_1,v_n) \neq r+1$
Also, vertices $x,v_l,v_{l+1},\ldots,v_m$ form a cycle $C : x,v_l,v_{l+1},\ldots,v_m,x$.
I need to show that by proposed construction Eccentricity of $x$ will not be $r$ if every or some vertices from the set $\{v_{l+1},\ldots,v_{m-1}\}$ are adjacent to $x$.
I felt I need to show that this cycle $C$ is of length less than $2r$. By taking particular values it is coming true but I am unable to prove it. And then distance between $x$ to $v_1$ or $v_n$ must be less than or greater than $r$ to prove the contradiction. Kindly help. Thanks for your timely help and guidance.
P.S. I tried to count the number of vertices from $v_l$ up to $v_m$ and it turned out to be $(m-l +1)$ number of vertices. But I am unable to proceed from here. How to show that $C$ contains less than $2r$ vertices?
The proof is given in three parts. In the first, we will come to the conclusion that $r \le 5$ must hold, which (together with restrictions in the problem) means only $r=4$ and $r=5$ are at all possible.
As next step, the case $r=5$ is handled. The conditions are used to more and more clarify the structure of a potential graph $H$ that fullfills the conditions, until only one graph remains. It is then shown that this graph contains a vertex with eccentricity > $r$, so no such graph $H$ actually exists.
Finally, $r=4$ is considered. The conditions can be used similar as in $r=5$, with a bit more leeway needing a few more steps. But again, it can be shown that any such graph must contain a vertex with eccentricity > $r$.
The 'new' vertex $x$ in $H$ allows a potential shortcut from $v_1$ to $v_n$ between $v_l$ and $v_m$ via $x$. So the length (number of edges) of the path $v_1, v_2, \ldots, v_l, x, v_m, v_{m+1},\ldots,v_n$ is
That makes the overall length of the path (which is equal to the distance of $v_1$ and $v_n$ in graph $H$, if we choose $m > l+1$) equal to $(l-1)+2+(n-m)=n+l-m+1$. With the assumption that
$$d(v_1,v_n)=n+l-m+1=r+1$$
we get $r=n+l-m$, or equivalently
$$m-l = n-r \tag{1}\label{eq1}.$$
From the problem statement we know that there might be more edges of the type $(x,v_i)$, with $l+1\le i \le m-1$.
We know that $x$ has eccentricity $r$ in $H$, so there is an index $k$ with $1\le k \le n$ with $d(x,v_k)=r$ and $d(x,v_i)\le r,\, \forall i=1,2,\ldots,n$.
Let's assume $k \le l$. Then obviously $d(x,v_k)=1+(l-k)$ (1 step from $x$ to $v_l$, then $l-k$ steps to $v_k$). In addition, $d(x,v_1) > d(x,v_i), \forall i=2,3,\ldots,l$, so we must have $k=1$ and hence $r=d(x,v_1)=l$.
Considering $\eqref{eq1}$ this implies the forbidden equality $m=n$. So we cannot have $v_k$ lie on the part of the graph that connects the first vertex $v_1$ to the cycle C=$(x,v_l,v_{l+1},\ldots,v_m,x)$.
In absolutely the same way one can show that $k \ge m$ implies first $k=n$, then $r=n-m+1$, which implies with $\eqref{eq1}$ that $l=1$, which is forbidden.
Both parts together mean that $l+1 \le k \le m-1$, or that $v_k$ lies on the cycle $C$ itself.
What's the distance of $v_l$ to $v_k$? It cannot be less then $r-1$. If it was less, we could prepend the edge from $x$ to $v_l$ to the path that realizes that small distance from $v_l$ to $v_k$, and get a path from $x$ to $v_k$ of length less than $r$, which is impossible. So we get
$$d(v_l,v_k) \ge r-1. \tag{2} \label{eq2}$$
Now we can show that $l$ must be less than $4$. If it was not, and we had $l\ge 4$, let's consider the distance from $v_2$ to $v_k$. Any path from $v_2$ to $v_k$ must necessarily pass through $v_l$. The part of the path from $v_2$ to $v_l$ has exactly $l-2$ edges, and the part from $v_l$ to $v_k$ has at least (see $\eqref{eq2}$) $r-1$ edges.
That means, taking into account that we assumed $l\ge 4$:
$$d(v_2,v_k) \ge (l-2)+(r-1) \ge 2+(r-1)=r+1,$$
which means that the eccentricity of $v_2$ is bigger than $r$, which is impossible, so we know that
$$l \le 3. \tag{3} \label{eq3}$$
Again one can make the same argument for the 'other end' of the original path $P_n$. We get
$$d(v_m,v_k) \ge r-1, \tag{4} \label{eq4}$$
in analgoy to $\eqref{eq2}$ and the assumption $n-m > 2$ leads to the impossible $d(v_{n-1},v_k) \ge r+1$. So we get the analogous inequality
$$n-m \le 2.\tag{5} \label{eq5}$$
From $\eqref{eq3}$ we get $m-l \ge m-3$ and from $\eqref{eq5}$ follows $m \ge n-2$, which combined means $m-l \ge n-5$. If we now look back at $\eqref{eq1}$, we find $n-r \ge n-5$, or equivalently $r\le 5$.
Let's consider the case $r=5$. That means both inequalities $\eqref{eq3}$ and $\eqref{eq5}$ must actually be sharp (equalities), so we have
$$l=3, m=n-2.$$
In addition both $\eqref{eq2}$ and $\eqref{eq4}$ must be sharp as well (otherwise we had $d(v_2,v_k)>r$ or $d(v_{n-1},v_k)>r$, resp):
$$d(v_l,v_k)=r-1=d(v_m,v_k)$$
No path of minimal length from $v_l$ to $v_k$ can go through $x$ (because if it would, we'd have an even shorter path from $x$ to $v_k$, which is impossible). That means such a minimal path can only exist in the original $P_n$ graph, which means that minimal path is simply $v_l,v_{l+1},\ldots,v_k$.
Considering that $r=5,l=3$ and $d(v_l,v_k)=r-1=4$, we get $k=7$. Note that no edge from $x$ to any of the nodes $v_4,v_5,v_6$ and $v_7$ may exist. If it would, we'd have $d(x,v_k)<r$, as assuming for example that edge $(x,v_4)$ exists, $x,v_4,v_5,v_6,v_7$ would be a path of lenght $4$ from $x$ to $v_k$.
Similiarly, no minimal path from $v_m$ to $v_k$ can pass through $x$, so whe have that the path $v_m,v_{m-1},\ldots,v_k$ has lenght $4$ and thus we get $m=11$ and $n=13$. Again, no edge from $x$ to any of $v_8,v_9,v_{10}$ may exist, as it would create a path from $x$ to $v_k=v_7$ that is shorter than $5$.
Summing this all up: For $r=5$ the only possibly graph is an $H$ with $n=13, l=3, m=11$ and no other edge from $x$ to any of the $v_i$, other than to $v_3$ and $v_{11}$ exists. This is just one graph, no variation possible.
It's easy to see that $d(v_6,v_{11})=5$ (both ways around the cycle $C$ have that length), and hence $d(v_6,v_{12})=6$, which contradicts the eccentricity condition.
Let's consider the remaining case $r=4$. The inequalities $\eqref{eq3}$ and $\eqref{eq5}$ cannot both be strict. If we had both $l \le 2$ and $m \ge n-1$ we'd get the impossible $r \le 3$, just as we did above when we proved $r\le 5$.
Let's assume w.l.o.g, that we have $l=3$ (the other case is totally symmetrical). Then we can have
Since $m \ge n-2$ and $m\neq n$, no other cases are possible.
Case 1 is handled exactly as for $r=5$. It can be proved exactly the same way that both $\eqref{eq2}$ and $\eqref{eq4}$ must be sharp. The only difference is that since $r=4$, we get $k=6$, then $m=9$ and $n=11$. Again one proves that $d(v_5,v_9)=4$ and $d(v_5,v_{10})=5>r$, which is a contradiction.
Let's consider case 2. Again $\eqref{eq2}$ must be sharp, with the same argument as before. As a side note, that argument doesn't work any more for $\eqref{eq4}$, because $v_{n-1}$ and $v_m$ are now one and the same vertex, in all previous cases they were different.
But with $\eqref{eq2}$ sharp, we can again conclude that the minimal length path from $v_2$ to $v_k$ must be $v_2,v_3,v_4,\ldots,v_k$ and hence we get $k=6$ and no edges from $x$ to $v_4,v_5$ or $v_6$ exist!
Since the path $x,v_{n-1},v_{n-2},\ldots,v_k$ cannot be shorter than length $4$, we have that the part from $v_{n-1}$ to $v_k$ cannot be shorter than length $3$, so we get $(n-1) - 6 \ge 3$, or $n\ge 10$. Again, no edge from $x$ to $v_7$ or $v_8$ may exist, as this shortens the distance from $x$ to $v_k=v_6$ below $4$.
That means any path from $v_5$ to $v_{n-1}$ has length at least 4. If one starts the path by going to $v_4$, the only option to continue is $v_3$, then $x$, then $v_{n-1}$ (length = $4$). If one starts the path in the other direction ($v_6$), one has again no other option than to go to $v_7,v_8$ and $v_9$ next. Since $n\ge 10$, that means after 4 steps we just arrived at $v_{n-1}$ (or even not yet, if $n > 10$).
So we have $d(v_5,v_{n-1}) \ge 4$ and hence $d(v_5,v_n) \ge 5$, which is against the eccentricity condition on $v_5$.
This concludes the proof!