Union of Two Trees $T_{1},T_{2}$ is also a tree when $T_{1}\cap T_{2}$ is connected Let $T_{1},T_{2}$ be two trees lying inside some common larger graph, say $G$. Under the hypothesis that $T_{1}\cap T_{2}$ is connected, is the union $T_{1}\cup T_{2}$ also a tree? This seems 'right' to me, but I've been unable to provide a proof of this intuitively 'right' assertion. Please help!
 A: I will first assume that when we intersect $T_1$ and $T_2$, we only take edges which belong to both, but not vertices. In this case the answer is no: $T_1\cup T_2$ might not be a tree: Take a square $\square$, and erase its upper edge to obtain $T_1$: $\sqcup$; and erase its right edge to obtain $T_2$: $\sqsubset$.
Now let's assume that we take both vertices and edges in the intersection $T_1\cap T_2$, in which case $T_1\cup T_2$ is a tree.
Take a path $x_1\cdots x_N$ in $T_1\cup T_2$. WLOG, say $x_1x_2\in T_1$. Choose numbers
$$1=n(1)<n(2)<\cdots<n(k)=N$$ such that for $n(i)\leq j<n(i+1)$, the edge $x_jx_{j+1}$ belongs to $T_{i\bmod 2}$ (where $i\bmod 2$ is simply the remainder of the division of $i$ by $2$).
In other words, we "break" the path $x_1\cdots x_N$ in pieces where the paths $x_{n(i)}x_{n(i)+1}\cdots x_{n(i+1)}$ belong to the same $T_j$.
In particular, for $2\leq i\leq k-1$, $x_{n(i)}\in T_1\cap T_2$, so for $2\leq i\leq k-2$ there is a path from $x_{n(i)}$ to $x_{n(i+1)}$ with edges in $T_1\cap T_2$. But by assumption, the $T_j$ are trees, so this path is necessarily $x_{n(i)}x_{n(i)+1}\cdots x_{n(i+1)}$, and in particular this path is inside $T_1$. It follows that the path $x_1x_2\cdots x_{n(k-1)}$ is inside $T_1$, and the path $x_{n(k-1)}\cdots x_{n(k)}$ is inside $T_2$. (Of course, the latter could be empty.)
This shows that each path $p$ in $T_1\cup T_2$ can be decomposed as $p=p_1p_2$, where $p_i$ is a path in some $T_j$.
Now take two paths $p$ and $q$ with same start and end-points we have a few cases:


*

*$p\subseteq T_1$
1.1. $q$ is completely inside $T_1$.
Then since $T_1$ is a tree, $p=q$;
1.2. $q=q_1q_2$, with $q_1\subseteq T_2$ nonempty.
Then the range and source of $q_1$ belong to $T_1\cap T_2$< so there is a path in $T_1\cap T_2$ connecting them. Since $T_2$ is a tree, this path is $q_1$, so $q_1\subseteq T_1$. We fall again in case 1.1.
1.3. $q=q_1q_2$ with $q_2\subseteq T_2$ nonempty.
This is similar to 1.2.

*$p\subseteq T_2$
This is similar to 1.

*$q\subseteq T_i$ for some $i$.
This is similar to case 1. or 2.

*$p=p_1p_2$ with $p_i\subseteq T_i$ nonempty.
4.1. $q=q_1q_2$ with $q_i\subseteq T_i$ nonempty.
In this case, the endpoints of $p_1$ and $q_1$ belong to $T_1\cap T_2$, so there is a path in $T_1\cap T_2$ connecting them. Since $T_1$ is a tree, this path is necessarily $p_1^{-1}q_1$, so it also belongs to $T_2$ and in particular both $p_1,q_1\subseteq T_2$. We fall in case 2.
4.2. $q=q_2q_1$ with $q_i\in T_i$ nonempty.
Then the start and end points of $p_1$ belong to $T_1\cap T_2$ and the usual argument implies $p_1\subseteq T_2$. We fall in case 2.

*$p=p_2p_1$ with $p_i\subseteq T_i$ nonempty.
This is similar to 4.
