how to prove helly property of a tree

Question

how can we prove by induction that a set of subtrees satisfies the Helly property of a tree T? i.e if a set of subtrees of T has the property that two of these subtrees have a common non-empty intersection, then the intersection of all the subtrees is also not empty

I have drawn out some trees to prove that this is true but I'm not sure how to formally write out the proof

Answer 1

First show that trivially it’s true if one of the subtrees has just one vertex. Then prove the following result by induction on the number of vertices in $T$:

Let $T$ be a tree, and let $\mathscr{T}$ be a finite family of subtrees of $T$ such that each $S\in\mathscr{T}$ has at least two vertices, and every pair of trees in $\mathscr{T}$ has non-empty intersection; then $\bigcap\mathscr{T}\ne\varnothing$.

Suppose that this is true for all trees with at most $n$ vertices, and let $T$ be a tree with $n+1$ vertices. Let $\mathscr{T}$ be a family of subtrees of $\mathscr{T}$ satisfying the conditions of the theorem. Let $v_0$ be a pendant vertex of $T$, let $v_1$ be its unique neighbor in $T$, and let $T'=T-v_0$. Let $\mathscr{T}'=\{S-v_0:S\in\mathscr{T}\}$.

• Show that if $S_0',S_1'\in\mathscr{T}'$, then $S_0'\cap S_1'\ne\varnothing$.

Now apply the induction hypothesis to $T'$ and the family $\mathscr{T}'$ to conclude that $\bigcap\mathscr{T}'\ne\varnothing$ and therefore $\bigcap\mathscr{T}\ne\varnothing$.