The trees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.

Question

Let $T_1, \ldots, T_k$ be subtrees of a tree $T$ such that for all $1 \leq i < j \leq k$, the trees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.

My demonstration. By induction on $n$, the order of $T$.

First, if $T$ has only one vertex, i.e., $n = 1$, the result is obvious: each of the $T_1, \ldots , T_k$ are in fact the only vertex of $T$. So the base case of induction is true. Suppose the statement is true for $m$. Let us consider a terminal vertex $v\in T$. Let us define $T':=T\setminus \{v\}$ which is a tree with $m$ vertices, and let us define $T_i':=T_i\setminus \{v\}$ which are also subtrees of $T'$. Let us check that for each $i\neq j$, $T_i'\cap T_j'\neq \emptyset$. We know by hypothesis that $T_i\cap T_j\neq \emptyset$; if this common vertex is not $v$, then it is a common vertex for $T_i'$ and $T_j'$. If the common vertex for $T_i$ and $T_j$ is $v$, then the vertex adjacent to $v$, say $u$, is a common vertex for $T_i'$ and $T_j'$. So the subtrees $T_1', \ldots , T_k'$ have a common vertex.

The induction hypothesis tells me that $T'$ has a vertex that is in all $T_i'$, and this is what must be concluded for $T$. I must see how to conclude from the information I already have, the existence of such a vertex in $T'$ and what I know by hypothesis for the $T_i$ and the $T_i'$.

Answer 1

I don't understand the problem. $T^\prime$ has a vertex $u$ which is in all of the $T_i^\prime.$ Since $u \in V(T_i^\prime),$ and $V(T_i^\prime) \subseteq V(T_i),$ it follows that $\in V(T\prime)\subset V(T)$ is in all of the $V(T_i)$

Answer 2

There appears to be the start of a good proof there. This is how you could finish building on what you already did.

By the inductive hypothesis, there is one common vertex $u$ in all of the nonempty $T'_i$. [Keep in mind that $v$ as you remove the vertex from $T$ the subtrees may get smaller as well and so there may be a $T'_i$ may have no vertices which implies that $T_i$ has exactly one vertex which is precisely the removed leaf vertex $v$.]

If on the one hand all of the $T'_i$s are nonempty, then $u$ is in all of the $T_i$s.

If on the other hand there is an $m$ such that $T'_m$ is empty, then $T_m$ [for that $m$ such that $T_m$ is empty] satisfies $T_m =\{v\}$. So by the assumption that every two $T_i,T_j$ intersect, it follows that every $T_i$ intersects $T_m =\{v\}$ which gives $v \in T_i$ for each such $i$. So if there is a $m$ such that $T'_m$ is empty, then it is $v$ that is in all of the $T_i$s.