Prove or disprove: If $P = x...y$ is a path in a $2$-connected graph $G$ then there is another $xy$-path $P'$, which is internally disjoint from $P$.

Question

Prove or disprove: If $P = x...y$ is a path in a $2$-connected graph $G$ then $G$ contains another $xy$-path $P'$, which is internally disjoint from $P$.

I'm not sure where to start with this. Any help is appreciated.

Answer 1

You can prove this by induction on the distance of $x$ and $y$.

Base case: If $dist(x,y)=1$, then $\{x,y\}$ is an edge. Let $z$ be a vertex different from $x$ and $y$. Since the graph is 2-connected, the removal of $x$ (respectively $y$) does not disconnect the graph, therefore there is a $(x,z)-$path $P_1$ which does not contain $y$, and a $(y,z)-$path $P_2$ which does not contain $x$. The $(x,y)-$path $P_1P_2$ is obviously internally disjoint from the trivial path $\{x,y\}$.

Inductive step: We assume that the statement holds for all pairs of vertices that have distance $\leq k$ and we take a pair of vertices $x$ and $y$ with $dist(x,y)=k+1$. Consider the shortest path from $x$ to $y$ and let $z$ be the vertex adjacent to $y$ on this path. Since $dist(x,z)=k$, from the inductive hypothesis we have that there are two internally disjoint $(x,z)-$paths, $P_1$ and $P_2$. Furthermore, we know that the removal of $z$ does not disconnect the graph, therefore there is a $(x,y)-$path $P_3$ that does not contain $z$. From there on it is easy to construct two internally disjoint $(x,y)-$paths using $P_1$, $P_2$ and $P_3$.