Two independent spanning trees of $2$-connected graph

Question

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?

Answer 1

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

Answer 2

Let's use a new concept oriented path in a cycle $C$ or an open ear $P_k$.

In $C$: Label the vertices in $C$ in clockwise direction by $u,v_1,\cdots,v_n$. Then the clockwise-oriented path of $C$ ($c_1$ path) is $uv_1\cdots v_n$, and the counterclockwise-oriented path of $C$ ($c_2$ path) is $uv_n\cdots v_1$.

In $P_k$: Since $P_k$ is open, it has two distinct vertices $x_1$ and $x_2$ intersecting with $\begin{cases} C \cup \bigcup_{j=1}^{k-1}P_j & k \geq 2 \\ C & k=1\end{cases}$. WLOG assume that by following $P_k$ in clockwise direction from $x_1$, we can reach $x_2$. Then label the vertices in $P_k$ in clockwise direction by $x_1,y_1,\cdots,y_\ell,x_2$. Then $c_1$ path of $P_k$ is $x_1y_1\cdots y_\ell$, and $c_2$ path of $P_k$ is $x_2y_\ell\cdots y_1$.

Now, we will construct two graphs $T_1$ and $T_2$: $T_1$ is a union of all $c_1$ paths of $C,P_1,\cdots,P_k$, and $T_2$ is a union of all $c_2$ paths of $C,P_1,\cdots,P_k$. And let's denote this event $E$.

1. $T_1$ and $T_2$ are connected. We deleted just one edge from a cycle or an ear to construct $c_1$ and $c_2$ path. It cannot disconnect $G$. Also, by the same reason, $T_1$ and $T_2$ are acyclic.

2. $V(T_1)=V(T_2)=V(G)$.

Thus, $T_1$ and $T_2$ are spanning tree of $G$.
We will use induction on $\vert V(G) \vert + \vert E(G) \vert$.

Basis: The smallest $2$-connected graph is $G=K_3$ with $\vert V(G) \vert + \vert E(G) \vert=6$. By applying $E$, $T_1=uv_1v_2$ and $T_2=uv_2v_1$. Obviously, it satisfies the given statement.

Induction hypothesis: Any graph $H$ with $\vert V(H) \vert + \vert E(H) \vert \leq m-1$ has two spanning trees obtained by $E$ such that for any $v \in U - \{u\}$, two $uv$-paths are independent. Note that since tree has a unique path between any pair of vertices, so we can assure that there are exactly two independent $uv$-paths, one from $T_1$ and another from $T_2$.

Now, for $2$-connected $G$, there is an open ear decomposition $(C,P_1,\cdots,P_k)$ of $G$. Let's delete edges in $P_k$ from $G$, and then delete isolated vertices. Let $G'$ be the resulting graph. By hypothesis, $G'$ has two spanning trees $T_1'$ and $T_2'$ made by $E$, containing two independent $uv'$-paths for any $v' \in V(G')-\{u\}$.

Since $P_k$ is an open ear, it has at least two vertices $x_1$ and $x_2$ intersecting with $G'$. As we did above, WLOG assume that we can reach $x_2$ from $x_1$ by following $P_k$ in clockwise direction. If $P_k$ is an edge, $T_1'$ and $T_2'$ are the desired trees. So assume $V(P_k) \geq 3$. Label the vertices in $P_k$ by $y_1,\cdots,y_n$ in clockwise direction. Now, by hypothesis, there are $ux_1$-path in $T_1'$ and $ux_2$-path in $T_2'$. Let $T_1=T_1' \cup x_1y_1\cdots y_n$ and $T_2=T_2' \cup x_2y_n\cdots y_1$. Then for any vertex $y_t$ in $P_k$, there are two $uy_t$-paths one from $T_1$ and another from $T_2$. Let's denote them $p_1$ and $p_2$ respectively.

1. Obviously, $p_1$ and $p_2$ does not intersect in $P_k$.
2. If they intersect at $z \in V(G')$, then among $p_1 \cup p_2$, two cycles appear. Let's denote $C_1$ a cycle containing $u$, and $C_2$ a cycle containing $y_t$. Since $C_2$ should be an open ear, there is another ear (or a union of ears) $P'$ having a path $q=zz_1\cdots z_s$ in common with $C_2$. But then we must attach $P'$ to $C_1$ before attaching $C_2$ to $C_1$ (or it's a closed ear). Then $C_2-q$ is an ear having intersection points $z$ and $z_s$ with $P'$. But then according to the algorithm, we cannot start drawing an oriented path from $z$, but have to start from $z_s$. Contradiction.

As a conclusion, $p_1$ and $p_2$ are independent. Now we obtained the desired $T_1$ and $T_2$ in $G$.