Problem 12.70 (Low Stretch Spanners). Spanning trees can be highways in road networks. On the right, the thick black edges are a spanning tree highway system. The other edges are nonhighways. The highway-only path between the green vertices has length 2, and there's no shorter path using all edges. For the red vertices, the shortest path-length is 1 , but the highway-only path has length 3. The path-stretch is the ratio of the highway-only to shortest path-lengths. The path stretch is 1 for the green vertices and 3 for the red vertices. (a) The stretch is the maximum path-stretch over all vertex-pairs. Compute the stretch of the spanning tree above. (b) Find a "best" spanning tree, having minimum stretch. (In general, this task is [HARD].) (c) What is worst case path stretch for a minimum stretch spanning tree. [Hint: Cn.] (d) Prove that the stretch of a spanning tree is at least 2 unless the graph is a already a tree. (e) Give a minimum stretch spanning tree for Kn. What is the stretch