How to prove this Tree/Set claim?

Question

If $T$ is a tree and $T_1, T_2, \ldots , T_k$ are all subtrees of $T$ such that the vertices of $T_i$ are $V_i$. Suppose $V_i\cap V_j$ is non-empty for all $i$ and $j$. Show that there is a vertex that exists in all $T_i$.

I'm honestly not even sure what the question is asking. This is just a completion grade, but I honestly do want to know how I should go about proving this. What method to use?

Answer 1

Let $F = \{V_1, \ldots, V_k\}$. We prove by induction on $j \in \{2, \ldots, k\}$ that:

Any $j$ vertex sets chosen from $F$ all share some vertex $v$ in common.

This is immediate for $j = 2$. For the inductive step, choose any $j$ vertex sets from $F$, say $W_1, \ldots, W_j$. By the inductive hypothesis, we know that for each $i \in \{1, \ldots, j\}$, there is some vertex $v_i \in W_1 \cap \cdots \cap W_{i-1} \cap W_{i + 1} \cap \cdots \cap W_j$. We claim that in the sequence of vertices $(v_1, \ldots, v_j)$, some two of them must repeat.

• Otherwise, if all $j$ vertices are distinct, then we can paste the following $j$ paths together to form a cycle, a contradiction:
  • The $(v_1, v_2)$-path in $T_3$ (which is guaranteed to exist since trees are connected).
  • The $(v_2, v_3)$-path in $T_4$.
  • $\cdots$
  • The $(v_{j-2}, v_{j-1})$-path in $T_j$.
  • The $(v_{j-1}, v_j)$-path in $T_1$.
  • The $(v_j, v_1)$-path in $T_2$.

Hence, we know that $v_a = v_b$ for some $a < b$. But then this vertex belongs to $W_1, \ldots, W_j$ as desired.

Answer 2

I can give a sketch of an inductive proof for this which can be expanded into a full proof.

The base case $ k = 1 $ is simple. Since all $V_1$ are in the tree $T_1$.

Now assume that this is true for $k$. There exists a $V_{bottleneck}$ in every $T_1,T_2,..$.

$T_{k+1}$ must have a shared note with each of $T_1,T_2,..$ however because trees are acyclic to get from any vertex in $T_1$ to a vertex in $T_2,T_3,...$ you have to travel through $V_{bottlenet}$.