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

A spanning tree is a connected acyclic subgraph containing every vertex of the original undirected graph. For a graph with $|V|$ vertices it has $|V|-1$ edges. A minimum spanning tree minimizes the sum of its edge weights over all spanning trees:Connectedness guarantees existence for a finite graph; equal weights can permit several minimizers.