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



Adding vertex-disjoint edges to reduce the diameter
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](https://mathoverflow.net/questions/202421/is-the-number-of-vertices-bounded-for-fixed-max-degree-and-fixed-diameter) it follows that
$$k=|V|\le1+3(1+2+4+\cdots+2^{n-2})=3\cdot2^{n-1}-2=k-1,$$
which is absurd.


