The intersection of $k$ subtrees of a tree $T$ is nonempty.

Question

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common.

Any hints/solutions are greatly appreciated. I am lost.

Answer 1

Use Proof by contradiction. Assume that at least three pairwise common vertices are distinct, then show that they form a cycle.

Answer 2

for k=3:

T3 contains node n1 from T1 and n2 from T2. Since T1 and T2 have a node in common this means that T1 + T2 contain the minimal subtree that connects n1 and n2. Since T3 contains n1 and n2, it means T3 also contains the minimal subtree that connects n1 and n2. So intersecting T1 T2 and T3 will result in at least 1 node from this minimal subtree. This proves that the statement is true for k= 3. Now you just have to generalize for any k.