Define the minimum spanning tree (MST) of a graph and justify, with counterexamples where appropriate, why the search for it makes sense only on connected, weighted and undirected graphs.

(b) Define these MST expressions: safe edge, cut, respecting a set of edges.

(c) Describe an efficient MST-finding algorithm, write some clear pseudocode for it and prove its correctness.

(d) Say whether each of the following two statements is true or false, justifying each answer with a proof or a counterexample.

(i) Graph G has a unique MST ? For every cut of G, the lightest edge that crosses it is unique.

(ii) Graph G has a unique MST ? For every cut of G, the lightest edge that crosses it is unique.