Past exam of the short options course of the University of Oxford / 2023 / 7 / a / i / Solution

A spanning tree of the connected graph $G$ is a subgraph containing every vertex, connected and without cycles in a graph. Equivalently, between every pair of vertices it has exactly one graph path. For a finite graph with $v$ vertices, it has $v-1$ edges.