Two independent spanning trees of $2$-connected graph

394 Views Asked by At

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?

1

There are 1 best solutions below

6
On BEST ANSWER

You could try building up two trees $T_1,T_2$ such that $V(T_1) = V(T_2)$ (here $V(T_i)$ denotes the vertex set of $T_i$), $u \in V(T_1)$ and for every vertex $v \in V(T_1) - \{u\}$ the $u-v$ paths in $T_1$ and $T_2$ are independent (i.e. internally disjoint).

At the beginning, let $T_1$ and $T_2$ consist of the single vertex $u$. Then while $V(T_1) \neq V$, choose an outgoing edge $e = u'v'$, where $u' \in V(T_1)$. Because $G$ is $2$-connected, you can find a path $P$ not containing $u'$ that goes from $v'$ to some vertex of $V(T_1)$ (Edit: as pointed out in the comments, this is not true for the first step and we need to modify the argument slightly in this case). Then you can use $P$ and $e$ to extend $T_1$ and $T_2$ to larger trees while maintaining the properties above.

The above strategy can be also rephrased as taking an open ear decomposition of $G$ whose initial cycle contains $u$, and then constructing two suitable spanning trees from the ear decomposition "one ear at a time".