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

Write each undirected edge with its smaller endpoint first. Kruskal's algorithm orders candidates first by weight and then lexicographically:Thus the requested addition order isand the minimum spanning tree has total weight $12$. Five accepted edges connect all six vertices, so the remaining weight-four edges need not be scanned.