Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 8 / a

For a finite connected graph $G=(V,E)$ with undirected edges and edge weights $w$, a spanning tree is a connected, acyclic subgraph containing all vertices. It has $|V|-1$ edges. A minimum spanning tree is one minimizing the sum of its edge weights:It minimizes total weight, rather than the distance of every route from a chosen root. Equal edge weights may permit more than one minimum spanning tree; negative weights do not invalidate the definition.