Suppose that a given graph \(G\) has edge weights that are all different, and that \(e\) is an edge in the minimum spanning tree of \(G\), but \(e\) is not the minimum-weight edge in \(G\). Describe how to construct a cut of the vertices of \(G\) into two subsets such that \(e\) crosses the cut, but is not the lightest edge across the cut. (Hint: use the minimum-weight edge.)
The "what we want to compute" slide of Wednesday's lecture notes shows a graph with 12 vertices and its minimum spanning tree. By the path property of minimum spanning trees, each path in this tree has the minimum bottleneck edge weight, among all paths between the same two vertices. Find a path in the graph that is not a path in the tree, but has the same property: it has the minimum bottleneck edge weight, among all paths between the same two vertices.
For the same graph as question 2, list the order that the 11 minimum spanning tree edges would be added to the tree by Jarník's algorithm, starting from the vertex in the bottom right corner of the graph.
For the graph of a cube (with eight vertices and twelve edges):
Give a system of weights, no two equal, for which Borůvka's algorithm constructs the minimum spanning tree in a single round of finding the smallest edge out of each component.
Give a system of weights, no two equal, for which Borůvka's algorithm takes three rounds.