I am given following problem as homework.
Let $G$ be a vertex obtained by attaching a pendant vertex $x$ to $K_n$ and $n\geq 3$. I need to show that I need at least $2r-2$ vertices to add to $G$ to obtain a graph $H$ so that the resulting graph has two vertices with eccentricity $r+1$ and rest with eccentricity $r$. also, $G$ induced in H$. I assumed the following cases.
It is clear that $diam(G) = 2$. Let $x$ be a pendant vertex attached to $K_n$ and $vx\in E(G)$ for some $v\in V(K_n)$. Let $H$ be an $r$-ASC embedding graph in which graph $G$ is induced. We have following two cases here depending upon eccentricity of vertex $x$ in $H$.
Case (a) $x$ is a diametral vertex of $H$, i.e. $e_H(x) = r+1$.
Proved by me.
Case (b) $x$ is not a diametral vertex in $H$, i.e. $e_H(x) = r$.
In this case, we have following subcases depending whether $K_n$ contains a diametral vertex or not.
Subcase (i) $K_n$ contains a diametral vertex, say $y$. Then there exists vertex $z$ in $H$ such that $d_H(y,z) = r+1$. Let $P: y=y_0,y_1,\ldots,y_{r+1} = z$ be a diametral path. Then $P_1$ contains at least $r-1$ vertices ($r+2-3 = r-1$, atmost three from $G$)
Subcase (ii) $K_n$ does not contain a diametral vertex.
How to move forward in the first subcase? Any hint or help will be highly appreciated. Thanks a lot for the help.