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
add comment

1 Answer

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.


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.

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
add comment

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.