Return to Answer

1. Obviouslty, $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$. WLOG assume that $q$ is in $T_1$. Then $q$ has a clockwise orientation $zz_1\cdots z_s$. Here, observe that we must attach $P'$ to $C_1$ before attaching $C_2$ to $C_1$. But then we have to give $q$ an orientation $z_s \cdots z_1z$. It's contradiction.

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.

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_\ell$ and $T_2=T_2' \cup x_2y_\ell\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.

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. How to construct it?

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

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

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 assuem 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_\ell$ and $T_2=T_2' \cup x_2y_\ell\cdots y_1$. Then for any vertex $y_t$ in $P_k$, there are two independent $uy_t$-paths one from $T_1$ and another from $T_2$. Let's denote them $p_1$ and $p_2$ respectively.

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

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_\ell$ and $T_2=T_2' \cup x_2y_\ell\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.