# A small help needed in proving a smart part of a result - to show that we need at least 2r-3 vertices to construct a particular type of graph.

I am given a graph $$G$$ with diameter two. I have to prove that I have to add minimum $$2r-3$$ vertices to $$G$$ to form a graph $$H$$ such that $$H$$ contains exactly two vertices with eccentricity $$r+1$$ (obviously peripheral vertices) and rest with eccentricity $$r$$ (central vertices), where $$r\geq 4$$. Also, $$G$$ is induced in $$H$$.

I am stuck at a particular part of the proof. Since diameter of $$G$$ is two, $$G$$ can at the most contain one diametral vertex or at the most one vertex with eccentricity $$r+1$$. I divided the proof in two cases. In first part, $$G$$ contains a vertex with eccentricity $$r+1$$. This part has been proved by me. In second case, $$G$$ does not contain a vertex with eccentricity $$r+1$$ and I am stuck in this case. However, I tried to prove it, but I am feeling that it is not surely true.

In the following attempt I consider a $$z-w$$ walk of length $$r$$ but I feel it is wrong as we already get a $$z-w$$ path of length $$r$$ lying on $$x-y$$ path since $$z$$ is adjacent to $$x$$.

MY ATTEMPT:

Let $$P$$ be a diametral path in $$H$$ of length $$r+1$$ with end vertices $$x$$ and $$y$$ ($$x,y\notin G$$).

Since $$diam(G) =2$$, at the most 3 vertices of $$G$$ can lie on $$P$$ and thus

$$P$$ contains at least $$r-1$$ new vertices. Since $$r\geq 4$$, $$r+1\geq 5$$ and $$P$$ contains at least six vertices. If $$x$$ and $$y$$ are end vertices of $$P$$ which are not in $$G$$ then there exists $$z\notin V(G)$$ and $$x\sim z$$ or $$y\sim z$$. Without loss of generality, let $$x\sim z$$. Since $$e(z)=r$$, there exists a $$z-w$$ path $$P_2$$ such that $$l(P_2)=r =d(z,w)$$. Now, the path $$P$$ can not be extended, otherwise $$d(x,y)>r+1$$, and $$P_2$$ contains at most three vertices from $$G$$. This follows that at least $$r-2$$ vertices in $$P_2$$ are not in $$G$$. This proves that we need to add at least $$(r-1) +(r-2) = 2r-3$$ new vertices.

Is this proof correct? I feel this proof is still incomplete. Somewhere I feel that I am missing some part. Kindly help me. Thanks a lot for your time and help.

P.S. It might be possible that $$P$$ and $$P_2$$ intersect at many vertices. In that case how to prove the result.

----------------------------------------------------

Added one more point in the proof (edited proof)

$$G$$ does not contain any diametral vertex.

Since $$diam(G) =2$$, here also $$P$$ contains at least $$r-1$$ new vertices. Since $$r\geq 4$$ and $$r+1\geq 5$$, $$P$$ contains at least six vertices. If $$x$$ and $$y$$ are end vertices of $$P$$ which are not in $$G$$ then there exists $$z\notin V(G)$$ and $$x\sim z$$ or $$y\sim z$$. Without loss of generality, let $$x\sim z$$. Since $$e(z)=r$$, there exists a $$z$$--$$w$$ path $$P_2: z,w_1,w_2,\ldots,w_r=w$$ such that $$l(P_2)=r =d(z,w)$$. Now, the path $$P$$ can not be extended, otherwise $$d(x,y)>r+1$$. Now, the $$P_2$$ contains at most three vertices from $$G$$ since $$diam(G) =2$$. Further, if $$P_2$$ intersect vertices of the $$P$$ then $$d(z,w), which is a contradiction because $$e(z) = r$$. This follows that at least $$r-2$$ vertices in $$P_2$$ are not in $$G$$.

• The question might get more attention if you rewrite the title to be more informative of what it is about. Commented Jun 24, 2019 at 13:07

Let $$v$$ be a vertex of $$G$$ with at least one neighbor among the new vertices. For $$i \in \{1,\ldots,r\}$$, let $$S_i$$ be the set of vertices at distance exactly $$i$$ from $$v$$. Note that $$S_1$$ and $$S_2$$ have at least one new vertex each. Suppose we show that all but one $$S_i$$ for $$i \geq 3$$ have at least two vertices. Then the number of new vertices is at least $$2(n-3)+1+2=2n-3$$. Let $$S_i=\{x\}$$ for some $$i$$. Then $$x$$ is a cut-vertex and it must be the case that its eccentricity is $$r$$, say component $$C$$ of $$H \setminus v$$ has $$y$$ such that $$d(x,y)=r$$, and $$V(H) \setminus (C \cup \{v\})$$ consists of one vertex of eccentricity $$r+1$$ which is a neighbor of $$x$$. This shows that there can be at most two cut-vertices in $$H$$, but hopefully this idea is sufficient to complete the proof with a more careful analysis.