CS180 Homework 4

1. Consider an undirected graph that weights of edges are distinct. We can define an order on the set of
spanning trees of the graph as follows: each spanning tree has n 1 edges, by sorting the weights of all
n 1 tree edges in the increasing order, we obtain a tuple (w1,…, wn1) where w1 < w2 < ... < wn1. We can easily define a lexicographic order on tuples by imagining that each tuple is a word with n 1 letter. More precisely, we say tuple (w0 1,..., w0 n1) is bigger than tuple (w1,..., wn1) if for the smallest index i at which w0 i 6= wi, we have w0 i > wi. We say tree T1 > T2 if T1’s tuple is lexicographically bigger than T2’s
tuple. We define the lexicographically minimum tree to be the smallest tree in this ordering of trees. Prove
that the lexicographically minimum tree is a minimum spanning tree.
2. Given an undirected graph with distinct weights. Consider a spanning tree for the graph: given any pair of
vertices u and v, the tree can be used to return a path between u and v such that maximum-weight edge
on the path has a smaller weight than the maximum-weight edge of any other path between u and v.
(a) Prove that the spanning tree with the above property is the minimum spanning tree (mst).
(b) We define a order between two paths A and B. We sort the weights of edges in the decreasing order and
A = {w1, w2,…, wi}, B = {w0
1, w0
2,…, w0
j
}. We say A is bottleneck-smaller than B, if the first different
weight edge in A has smaller weight than the edge in B, more precisely if for the smallest index k
in A at which w0
k 6= wk, we have wk