# Proofs involving subtrees of a tree

I have found some claims about trees in my graph theory text, and I am wondering if corresponding proofs can be found, as I cannot find any online or in another text.

First,

If $T_1$ and $T_2$ are subtrees of tree $T$ such that $V_{T_1} \cap V_{T_2} \neq \emptyset$, then $T_1 \cap T_2$ is a subtree of $T$.

Further, this appears to be an expansion of the above claim:

If $T_1, T_2, T_3$ are subtrees of $T$ with vertex sets $V_1, V_2, V_3$ such that $V_i \cap V_j \neq \emptyset$ for each $i, j$, then $V_1 \cap V_2 \cap V_3 \neq \emptyset$ and $T_1 \cap T_2 \cap T_3$ is a subtree of $T$.

-

A tree is a graph that is connected and does not contain any cycles. Since $T_1 \cap T_2$ is a subgraph of both $T_1$ and $T_2$, which are trees, it can obviously not contain cycles.

What remains to be shown is that $T_1\cap T_2$ is still connected. Fix two vertices $v_1, v_2$ in $T_1\cap T_2$. Obviously, we then also have $v_1, v_2\in T_1$ and $v_1, v_2\in T_2$. Furthermore, we assumed $V_{T_1}\cap V_{T_2}\neq \emptyset$. Let therefore $v$ be a vertex in $V_{T_1}\cap V_{T_2}$ (and thus also in the graphs $T_1$, $T_2$, and $T_1\cap T_2$).

Since $v_1$ and $v$ (resp. $v_2$ and $v$) are in $T_1$ (resp. $T_2$) and $T_1$ (resp. $T_2$) are connected, there is a path from $v_1$ to $v$ (resp. from $v_2$ to $v$). By combining these paths, we also have a path from $v_1$ to $v_2$.

Therefore, $T_1\cap T_2$ is connected, and because of its cycle-freeness, it is then also a tree.

The second claim, in its current form, is false, if I see this correctly. Consider the complete graph $K_3$ with vertices $\{1,2,3\}$ and edge set $\{(i,j)\ |\ i,j \in \{1,2,3\}\}$. Choose $V_1=\{1,2\}$, $V_2=\{2,3\}$, $V_3=\{1,3\}$. Then, obviously, all the premises of the claim hold, but $V_1\cap V_2\cap V_3=\emptyset$.

I suggest the following theorem instead:

If $T_1,T_2,T_3$ are subgraphs of a tree $T$ with vertex sets $V_1,V_2,V_3$ and $V_1\cap V_2\cap V_3\neq \emptyset$, then $T_1\cap T_2\cap T_3$ is also a tree.

This can easily be reduced to the first claim you posted, by applying it twice. In fact, this can be generalised to arbitrarily many trees and their intersection.

-
It’s clearly a typo: each pair of vertex sets should have non-empty intersection. –  Brian M. Scott Mar 20 '13 at 3:17
Even then, I see counterexamples: consider the complete graph $K_3$ with vertices {1,2,3} and edge set {(i,j) | i,j ∈ {1,2,3}}. Choose V1={1,2}, V2={2,3}, V3={1,3}. All premises hold, but the intersection of all three vertex sets is empty. –  Manuel Eberl Mar 20 '13 at 3:20