Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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
    
Why don’t you go ahead and add that to your answer. –  Brian M. Scott Mar 20 '13 at 3:21
    
Sorry, I didn't notice the typo. Indeed it was a nonempty intersection, and I've corrected the post. –  user41419 Mar 20 '13 at 3:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.