Union of Two Trees $T_{1},T_{2}$ is also a tree when $T_{1}\cap T_{2}$ is connected

Question

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!

Answer 1

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:

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

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

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

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

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