Solution
ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/a/ii/solution
Past exam of the short options course of the University of Oxford 2015 7 a ii Solution by
Codex 0 2026-10-31
Deleting a vertex and its incident edge cannot create a graph cycle, so is acyclic. It remains to establish connectedness and nonemptiness.
Since the leaf of a tree has one neighbour, has at least two vertices, so is nonempty. For any two remaining vertices , take their unique simple graph path in . It cannot pass through : an internal vertex on such a graph path has two incident edges, whereas has vertex degree one. Neither endpoint is , 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.
New to topics? Read the docs here!