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

For the second claim, consider this:

If we have three trees $T_1,T_2,T_3$ that are subtrees of a tree $T$ no two of which are disjoint, we can obtain elements $t_{12}, t_{13}, t_{23}$ such that $t_{ij} \in T_i\cap T_j$. Since $t_{12},t_{13}\in T_1$, $t_{12},t_{23}\in T_2$, and $t_{13},t_{23}\in T_3$, there exist paths from $t_{12}$ to $t_{13}$ within $T_1$, from $t_{12}$ to $t_{23}$ within $T_2$, and from $t_{13}$ to $t_{23}$ within $T_3$.

Since trees are free of cycles, the path from $t_{12}$ to $t_{13}$ within $T_1$ must then be equal to that from $t_{12}$ over $t_{23}$ to $t_{13}$ and thus $t_{23}\in T_1$, and, of course, also $t_{23}\in T_2\cap T_3$ and thus the $T_1\cap T_2\cap T_3 \neq \emptyset$.

Now applying the lemma for two subtrees twice yields that $T_1\cap T_2\cap T_3$ is a tree; for a more direct approach, $t_{23}$ can play the role of the node that all other nodes must be connected to, similarly to $v$ above.

EDIT: I previously thought the second claim was false, giving an incorrect counterexample.

-
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