Adding vertex-disjoint edges to reduce the diameter

Question

Let $G=(V,E)$ be a finited connected graph, $V\neq \emptyset$. Let $[V]^2 := \big\{ \{v,w\}: v, w \in V\text{ and } v\neq w\big\}$. Given $F\subseteq [V]^2$ we say that $F$ is a vertex-disjoint extension of $E$ if

• $F\supseteq E$, and
• $f_1\neq f_2\in (F\setminus E)$ implies $f_1\cap f_2 = \emptyset$.

Given $n\in\mathbb{N}$, is there a connected graph $G=(V,E)$ such that for every vertex-disjoint extension $F$ of $E$ we have $\text{diam}(V,F) \geq n$?

Answer 1

Yes. Let $G=(V,E)=P_k$, the $k$-point path, where $k=3\cdot2^{n-1}-1$, and let $F$ be any vertex-disjoint extension of $E$; I claim that the graph $H=(V,F)$ has radius $\operatorname{rad}(H)\ge n$.

Assume for a contradiction that $\operatorname{rad}(H)\le n-1$. Since $\Delta(H)\le3$, by the answer to this question it follows that $$k=|V|\le1+3(1+2+4+\cdots+2^{n-2})=3\cdot2^{n-1}-2=k-1,$$ which is absurd.