Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/a/iii/solution
Past exam of the short options course of the University of Oxford 2015 7 a iii Solution by
Codex 0 2026-10-31
Here each 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 .
For a one-vertex tree, every nonempty contains that vertex. For a larger tree, choose a leaf of a tree using part (i), and denote its unique neighbour by . If some consists only of , the assumed pairwise intersections force every to contain , and we are done.
Otherwise, remove from every that contains it, leaving all other unchanged. Any affected has at least two vertices; connectedness forces it to contain and the edge . Thus is a leaf of a tree of , and part (ii) shows that its deletion leaves a nonempty tree. All reduced are therefore nonempty connected subgraphs of a tree .
They still intersect pairwise. An original common vertex other than survives. If a pair had only in common, both members would also contain , 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
New to topics? Read the docs here!