In an undirected weighted graph, recall that the width of a path is the minimum weight of one of its edges, and define the width of a cut to be the maximum weight of one of its edges. Prove that, for every two vertices $s$ and $t$, the width of the widest path from $s$ to $t$ equals the width of the narrowest cut separating $s$ from $t$ (the cut with the smallest possible width). Hint: Use the fact that the maximum spanning tree contains the widest path to find a cut with this width. You may assume that no two edges have equal weights if it simplifies your proof.
The graph of a cube has eight vertices and twelve edges. Find weights for these edges such that Boruvka's algorithm takes three iterations to construct the minimum spanning tree of the graph.
(163 only): Find a weighted undirected graph $G$, and a minimum spanning tree $T$ of $G$, such that at least one of the minimum weight edges in $G$ does not belong to $T$. Explain why this does not violate the cut property of minimum spanning trees described in class.
(265 only): Let $G$ be a graph in which all edge weights are positive. Describe a method for constructing a spanning tree that maximizes the product of the edge weights (instead of their sum). Explain why your method is correct.
(163 only): Describe how to modify Kruskal's algorithm to compute a maximum spanning tree instead of a minimum spanning tree.
(265 only): Describe how to modify the maximum-spanning-tree version of Kruskal's algorithm to compute a widest cycle in a given weighted undirected graph. (That is, among all simple cycles, we want the one whose lightest edge is as heavy as possible.)