11.11. References 471
(c)Assume thatDsatisfies equation (11.9). Show that it is possible to partition
Dinto two setsS 1 ;S 2 such that the sum of the elements in each set is the same.
Hint:Trees are bipartite.
Problem 11.70.
Prove Corollary 11.10.12: If all edges in a finite weighted graph have distinct
weights, then the graph has auniqueMST.
Hint:SupposeMandNwere different MST’s of the same graph. Letebe the
smallest edge in one and not the other, saye 2 M N, and observe thatNCe
must have a cycle.