Return to Answer

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

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

I think this is false for $K_{2,n}$. I will write a proof down soon.

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

Yes, this is true. 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$ is just a cycle, then the claim is true (see the comment of okw1124 above), so we may assume that $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$. Since $G'=G-\{x_2, \dots, x_{\ell-1}\}$ is $2$-connected, $G'$ contains two spanning trees $T_1'$ and $T_2'$ such that for all $v \in V(G') \setminus \{u\}$, the $uv$-paths in $T_1'$ and $T_2'$ are internally-disjoint. Let $T_1=T_1' \cup x_1x_2 \dots x_{\ell-1}$ and $T_2:=T_2' \cup x_2x_3 \dots x_\ell$. It suffices to show that for all $v \in \{x_2, \dots, x_{\ell-1}\}$, the $uv$-paths in $T_1$ and $T_2$ are internally-disjoint. This follows from the fact that the $ux_1$-paths in $T_1$ and $T_2$ are internally-disjoint, the $ux_\ell$-paths in $T_1$ and $T_2$ are internally-disjoint, and the two paths $x_1 x_2 \dots v$ and $x_\ell x_{\ell-1} \dots v$ are internally-disjoint.

I think this is false for $K_{2,n}$. I will write a proof down soon.