Solution

ID: past-exam-of-the-short-options-course-of-the-university-of-oxford/2015/7/a/ii/solution

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, giving
This includes the two-vertex case, where deletion leaves the one-vertex tree.

New to topics? Read the docs here!