Prove that sub-trees have a common vertex

1k Views Asked by At

OK so this is a bonus question I got that I would really like to solve because I have been sitting on it for an hour without any progress. Any direction from you guys would be very helpful:

Let $T$ be a tree with $n$ vertices, and let $T_1,T_2,...,T_k$ be sub-trees of $T$. So $T_i=(V_i,E_i)$ for every $1\le i\le k$. Also, for every $1\le i\lt j\le k$, let's suppose that $V_i\cap V_j\neq\emptyset$. Prove that $\bigcap_{i=1}^kV_i \neq \emptyset$.

1

There are 1 best solutions below

6
On BEST ANSWER

Hint:

Prove the slightly stronger result that $\bigcap T_i$ is a subtree of $T$. This can be proved by induction on $k$.