For all $1 \leq i < j \leq k$, the subtrees $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

Can someone please verify my proof or offer suggestions for improvement? I am aware that there is a similar question elsewhere, but I want help with my proof in particular.

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$.

Suppose, for the sake of contradiction, that for every vertex $v \in V(T)$, there is a subtree $T'$ in the list $T_1, T_2, \ldots, T_k$ such that $v \notin V(T')$.

Pick $v_1 \in T_1$. There is a subtree $T^{(1)}$ such that $v_1 \notin T^{(1)}$. $T_1$ and $T^{(1)}$ have a vertex $y_1$ in common. Now, there exists a tree $T^{(2)}$ such that $y_1 \notin T^{(2)}$. But now, $T^{(2)}$ and $T^{(1)}$ have a vertex $y_2$ in common. Also, $T_1$ and $T^{(2)}$ have a vertex $y_3$ in common.

There exists a path $p_1$ in $T_1$ from $y_3$ to $y_1$. Also, there is a path $p_2$ in $T^{(1)}$ from $y_1$ to $y_2$ and a path $p_3$ in $T^{(2)}$ from $y_2$ to $y_3$. Note that the path formed by the union of $p_1$ and $p_2$ passes through $y_1$, while $p_3$ does not, since $y_1 \notin T^{(2)}$. Therefore, the union of $p_1, p_2$, and $p_3$ forms a cycle, contradicting the fact that $T$ is a tree. Therefore, it must be the case that there is a vertex $x$ in all of the $T_i$.

Answer 1

This proof is not correct. Apart from the fact that you mix-up $T_1$ and $T^{(1)}$ there is a logic error: the statement "Therefore, the union of $p_1$, $p_2$, and $p_3$ forms a cycle" needs justification. You need an argument to exclude an example like: $p_1=y_1vwy_3$ and $p_2=y_1vwy_2$ and $p_3=y_2wy_3$.

Answer 2

Let $T_1'$ be a minimal subtree of $T_1$ such that $V(T_1')\cap V(T_j)\ne\emptyset$ for all $j\in\{1,\dots,n\}$. If $T_1'$ has only one vertex, we're done. Assume for a contradiction that $T_1'$ has more than one vertex. Then $T_1'$ has at least two leaves; let $x$ and $y$ be two distinct leaves of $T_1'$. By the minimality of $T_1'$, there are indices $i$ and $j$ such that $V(T_i)\cap V(T_1')=\{x\}$ and $V(T_j)\cap V(T_1')=\{y\}$. Since $T_i$ and $T_j$ have a common vertex, their union $T_i\cup T_j$ is connected. Let $P$ be the path from $x$ to $y$ in $T_i\cup T_j$, and let $Q$ be the path from $x$ to $y$ in $T_1'$. Since $V(P)\cap V(Q)=\{x,y\}$ and $E(P)\cap E(Q)=\emptyset$, $P\cup Q$ is a cycle in $T$, contradicting the assumption that $T$ is a tree.

P.S. In the question and answer above, trees are assumed to be finite. In a comment SK19 suggested generalizing the result to infinite trees. SK19 pointed out that the result fails if $T_1,T_2,\dots$ is an infinite decreasing sequence of rays (one-way infinite paths) with empty intersection. This is essentially the only counterexample.

In what follows, trees may be finite or infinite. A tree is rayless if it does not contain a sequence of distinct vertices $v_n$ ($n\in\mathbb N$) with $v_n$ adjacent to $v_{n+1}$ for each $n$.

Lemma. A chain of rayless trees has a nonempty intersection. (The intersection, of course, is a tree.)

Proof. Assume for a contradiction that $\mathcal C$ is a chain of rayless trees whose intersection is empty. Choose a tree $T_0\in\mathcal C$ and a vertex $x_0\in V(T_0)$. Having chosen a tree $T_n\in\mathcal C$ and a vertex $x_n\in V(T_n)$, next choose a tree $T_{n+1}\in\mathcal C$ not containing $x_n$ (so $T_{n+1}$ is a subtree of $T_n$ since $\mathcal C$ is a chain), and let $P_n$ be the path in $T_n$ from $x_n$ to $x_{n+1}$. As the paths $P_0,P_1,P_2,\dots$ are internally disjoint, by concatenating them we get a ray in $T_0$, contradicting the fact that $T_0$ is rayless.

Theorem. Let $(T_i:i\in I)$ be a family of subtrees of a tree $T$. The intersection $\bigcap_{i\in I}V(T_i)$ is nonempty if and only if both of the following statements hold:
(a) $V(T_i)\cap V(T_j)\ne\emptyset$ for all $i,j\in I$;
(b) there is a rayless subtree $S$ of $T$ such that $V(S)\cap V(T_i)\ne\emptyset$ for all $i\in I$.

Proof. The "only if" is clear; we prove the "if". Suppose (a) and (b) hold; we have to show that $\bigcap_{i\in I}V(T_i)\ne\emptyset$.

Let $\mathcal P$ be the set of all subtrees $S'$ of $S$ such that $V(S')\cap V(T_i)\ne\emptyset$ for all $i\in I$. Then $\mathcal P$ is nonempty because $S\in\mathcal P$. Moreover, it follows from our lemma that every chain $\mathcal C\subseteq\mathcal P$ has a lower bound in $\mathcal P$, namely its intersection. (For $i\in I$, $\{S'\cap T_i:S'\in\mathcal C\}$ is a chain of rayless trees.) Therefore, by Zorn's lemma, $\mathcal P$ has a minimal element. Let $S_0$ be a minimal element of $\mathcal P$.

If $S_0$ has only one vertex, we're done. Assume for a contradiction that $S_0$ has more than one vertex. Then, since $S_0$ is rayless, it has at least two leaves (the endpoints of any maximal path in $S_0$); let $x$ and $y$ be two distinct leaves of $S_0$. By the minimality of $S_0$, there are indices $i,j\in I$ such that $V(T_i)\cap V(S_0)=\{x\}$ and $V(T_j)\cap V(S_0)=\{y\}$. Since $T_i$ and $T_j$ have a common vertex, their union $T_i\cup T_j$ is connected. Let $P$ be the path from $x$ to $y$ in $T_i\cup T_j$, and let $Q$ be the path from $x$ to $y$ in $S_0$. Since $V(P)\cap V(Q)=\{x,y\}$ and $E(P)\cap E(Q)=\emptyset$, $P\cup Q$ is a cycle in $T$, contradicting the assumption that $T$ is a tree.

Corollary. Let $(T_i:i\in I)$ be a family of subtrees of a tree $T$ such that $V(T_i)\cap V(T_j)\ne\emptyset$ for all $i,j\in I$. If $I$ is finite, or if $T_i$ is rayless for some $i\in I$, then $\bigcap_{i\in I}V(T_i)\ne\emptyset$.

Answer 3

It suffices to prove the following lemma:

$\textbf{Lemma.}$ If $T_1, T_2, T_3$ are subtrees of a tree $T$ such that any two intersection is not empty, then all $3$ subtrees have a common vertex.

$\textbf{Proof.}$ Suppose no vertex lies in all $3$ trees. Then there exist distinct vertices $w_1, v_2, v_3$ in $T_2\cap T_3, T_3\cap T_1, T_1\cap T_2$ respectively, none of which belongs to their respective third tree.

So there exist a path $P \in T_3$ from $w_1$ to $w_2$. In this (unique) path, choose two vertices $x$ and $y$ in $P$ such that $x\in T_1$ and $y\in T_2$, and any vertex between $x$ and $y$ along $P$ are not in $T_1\cup T_2$. Note that $x$ and $y$ must necessarily be distinct by assumption, but are allowed to be adjacent.

Then we can define a path $Q$ from $x$ to $y$ in $T_1\cup T_2$, by taking the shortest path from the walk $x$ to $w_3$ to $y$ in $T_1\cup T_2$. This path $Q$ is disjoint from $P$ so $P\cup Q$ forms a cycle, a contradiction with $T$ being acyclic. $\square$

The problem now follows by induction: Suppose this is true for some $k\ge 3$, with base case $k=3$ proven above. Given $k+1$ subtrees with the given conditions, notice that for any $1\le i < j \le k$, $T_i\cap T_j$ is also a subtree of $T$. Indeed, if $x$ and $y$ are vertices in $T_i\cap T_j$, then take the unique path $P$ in $T$ from $x$ to $y$, $P$ must be in both $T_i$ and $T_j$ for it to be subtrees of $T$.

Now, note that by the lemma, $T_i\cap T_{k+1}$ and $T_j\cap T_{k+1}$ have a common vertex for all $i\neq j$, and are all subtrees of $T$. So we can apply the hypothesis on these subtrees to conclude they have a common vertex, hence so as the subtrees $T_1,\cdots T_{k+1}$. $\blacksquare$