Skip to main content
2 of 3
Previous answer was incorrect.
benblumsmith
  • 2.9k
  • 18
  • 26

If I understand the question correctly and $H$ is finite, the answer is yes.

(I first thought the answer is no and started to give counterexamples; then realized all my counterexamples failed for the same reason.)

Let $H$ be a graph with the stated property: for each edge $e$, there is a pair of vertices $u,v$ and a path from $u$ to $v$ containing $e$ and of length $\leq 2$ that is the unique path of length $\leq 2$ (up to orientation, I assume) between $u,v$. (Let us shorthand this by writing $P(e)$ for the assertion that for edge $e$ there exists such a path and "$H$ has property $P$" means $P(e)$ is satisfied for every $e\in E(H)$.)

I assert that if $H$ has diameter $> 2$, then an edge can be added that preserves property $P$ and the diameter of the new graph is $>1$. Since adding an edge cannot increase the diameter and can only be done a finite number of times before the diameter becomes $1$, this shows inductively that one will arrive at the desired graph $G$ of diameter $2$ and having property $P$.

If $H$ has diameter $>2$, then there is a pair of vertices $u,v$ with no path of length $\leq 2$ between them. Add the edge $(u,v)$.

I claim that the new graph $H'$ has the desired property $P$. First, the path $(u,v)$ is the unique path of length $\leq 2$ between $u$ and $v$, so the new edge has the desired property. Secondly, all other edges $e'\in E(H')\setminus (u,v) = E(H)$ satisfy $P(e')$ in $H'$. To see this: as $e'$ is an edge of the original graph $H$, $P(e')$ is true in $H$, so there is a pair of vertices in $V(H)$ with a path containing $e'$ of length $\leq 2$ that is the unique such path between them in $H$. If there is another such path in the augmented graph $H'$, then it must go through $(u,v)$. Then the two paths together give a cycle of length $\leq 2+2=4$, containing $(u,v)$. By the assumption that $u,v$ are not linked by a path of length $\leq 2$ in $H$, it must be that this cycle (call it $C$) has length exactly 4 and $u,v$ were linked by a path of length $3$ in the original graph $H$, and $e'$ is one of the three edges of this path. But then the path consisting of $e'$ itself witnesses $P(e')$: if the vertices of $e'$ are $x$ and $y$ (one of them could be $=u$ or $v$, or not), then a path linking $x$ and $y$ but avoiding $e$ has length at least $3$: if it lies entirely in $H$ this is true by the assumption about $H$, while if it goes through $(u,v)$ then it plus $e'$ give a cycle containing $(u,v)$ which must be length at least $4$.

Finally, $H'$ still has diameter $>1$ because it is not a complete graph (since a complete graph does not have property $P$). This completes the argument.

benblumsmith
  • 2.9k
  • 18
  • 26