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.