Skip to main content
4 of 5
added 1729 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, this is true. We will prove the following stronger lemma.

Lemma. Let $G$ be a $2$-connected graph and $u \in V(G)$. Then $G$ contains two spannings trees $T_1$ and $T_2$ such that for all $a,b \in V(G) \setminus \{u\}$ (possibly $a=b$), either

  • the $ua$-path in $T_1$ and the $ub$-path in $T_2$ are internally-disjoint, or
  • the $ub$-path in $T_1$ and the $ua$-path in $T_2$ are internally disjoint.

Proof. We proceed by induction on $|V(G)|+|E(G)|$. Since $G$ is $2$-connected, $G$ has an ear decomposition $(C, P_1, \dots, P_k)$, with $u \in V(C)$. If $G=C$, let $e_1$ and $e_2$ be the two edges incident to $u$. It is easy to check that we may take $T_1=C \setminus e_1$ and $T_2=C \setminus e_2$. Thus, we may assume $k \geq 1$. If the last ear $P_k$ is just an edge $e$, then $G \setminus e$ is $2$-connected, and we can apply induction. Thus, we may assume $|V(P_k)| \geq 3$. Suppose $P_k=x_1x_2 \dots x_\ell$. Observe that $G'=G-\{x_2, \dots, x_{\ell-1}\}$ is $2$-connected. By induction, $G'$ contains two spanning trees $T_1'$ and $T_2'$ such that for all $a,b \in V(G') \setminus \{u\}$, either

  • the $ua$-path in $T_1'$ and the $ub$-path in $T_2'$ are internally-disjoint, or
  • the $ub$-path in $T_1'$ and the $ua$-path in $T_2$' are internally disjoint.

In particular, either

  • the $ux_1$-path in $T_1'$ and the $ux_\ell$-path in $T_2'$ are internally-disjoint, or
  • the $ux_\ell$-path in $T_1'$ and the $ux_1$-path in $T_2$' are internally disjoint.

In the first case, $T_1:=T_1' \cup x_1x_2 \dots x_{\ell-1}$ and $T_2:=T_2' \cup x_2x_3 \dots x_\ell$ are the required spanning trees of $G$. In the second case, $T_1:=T_1' \cup x_2x_3 \dots x_\ell$ and $T_2:=T_2' \cup x_1x_2 \dots x_{\ell-1}$ are the required spanning trees of $G$.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187