Past exam of the short options course of the University of Oxford / 2015 / 7 / a

A tree is a nonempty connected graph with no graph cycle. A leaf of a tree is a vertex of vertex degree one. As usual in this finite graph theory problem, trees are finite; the assertion would fail for a doubly infinite graph path.

Take a longest path $v_0,v_1,\dots ,v_m$ in a tree with at least two vertices. Connectedness gives $m\ge 1$. If $v_0$ had a neighbour outside this graph path, the path could be extended, contradicting maximal length. If it had a neighbour $v_j$ with $j\ge 2$, that edge together with the segment $v_0,v_1,\dots ,v_j$ would make a graph cycle. Thus its only neighbour is $v_1$, and it is a leaf of a tree. The same argument at the other end makes $v_m$ a second, distinct leaf of a tree. Hence

Deleting a vertex and its incident edge cannot create a graph cycle, so $T\setminus v$ is acyclic. It remains to establish connectedness and nonemptiness.

Since the leaf of a tree $v$ has one neighbour, $T$ has at least two vertices, so $T\setminus v$ is nonempty. For any two remaining vertices $a,b$, take their unique simple graph path in $T$. It cannot pass through $v$: an internal vertex on such a graph path has two incident edges, whereas $v$ has vertex degree one. Neither endpoint is $v$, so the entire graph path remains after deletion. The remaining graph is connected and acyclic, givingThis includes the two-vertex case, where deletion leaves the one-vertex tree.

Here each $T_i$ is a nonempty connected subgraph of a tree, rather than a descendant-closed data-structure subtree. We prove the Helly property for connected subgraphs of a tree by mathematical induction on the number of vertices of $T$.

For a one-vertex tree, every nonempty $T_i$ contains that vertex. For a larger tree, choose a leaf of a tree $v$ using part (i), and denote its unique neighbour by $w$. If some $T_i$ consists only of $v$, the assumed pairwise intersections force every $T_j$ to contain $v$, and we are done.

Otherwise, remove $v$ from every $T_i$ that contains it, leaving all other $T_i$ unchanged. Any affected $T_i$ has at least two vertices; connectedness forces it to contain $w$ and the edge $vw$. Thus $v$ is a leaf of a tree of $T_i$, and part (ii) shows that its deletion leaves a nonempty tree. All reduced $T_i$ are therefore nonempty connected subgraphs of a tree $T\setminus v$.

They still intersect pairwise. An original common vertex other than $v$ survives. If a pair had only $v$ in common, both members would also contain $w$, by the previous paragraph, contradicting that it was their only common vertex. The induction hypothesis now supplies a common vertex of the reduced family, which is also common to the original family. Consequently