I want to prove the following statement:
Let $u$ be a vertex in a $2$-connected graph $G$. Then $G$ has two spanning trees such that for every vertex $v$, the $u,v$-paths in the trees are independent.
I tried to show this, but surprisingly, I have proved another statement.
A graph with $\vert V(G) \vert \geq 3$ is $2$-connected iff for any two vertices $u$ and $v$ in $G$, there exist at least two independent $u,v$-paths.
And I can assure that it is true, since I could find it from other papers.
I think this one may help me proving the desired statement, but I have no idea how to use it properly.
Would you help me find a such way, or suggest another proof of the first statement?
Best 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
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
In particular, either
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$.