115 pts] Consider a connected, undirected, edge weighted graph G with n vertices and e edges. For any spanning tree T of G, a bottleneck edge of T is an edge of largest weight in T. A bottleneck spanning tree for G is a spanning tree for G which, among all spanning trees for G, has the smallest weight bottleneck edge. 1. [10 pts] Prove that a minimum spanning tree is also a bottleneck spanning tree. You may want to make use of this a) OBSERVATION: Kruskal's algorithm does not use the edge weights except to produce a sorted list of the edges. Imagine then that we have two graphs Gi and G2 with identical vertices and edges where the weights in G2 are identical to the weights in Gi except for the largest k edges (for some k). For those k edges, let the weights in G2 each be L larger than the weights in Gi. This means that edges appear in the same order in the sorted edge lists for Gi and G2, hence the same edges will be selected for the MSTs in Gi and G2. Note too that L could be HUGE and the conclusion would still be the same HINT: Assume by way of contradiction that some MST T of G is not a bottleneck spanning tree (BST) of G. This means that the largest edge in T is larger than e, a bottleneck edge in a BST TB of G. Construct a new graph G' such that G' and G have the same edge set in their MSTs, albeit edges of different weights. Use the OBSERVATION and the tree TB to argue that a contradiction ensues b) [5 pts] Give an example showing that the reverse is not necessarily true. That is, show that a bottleneck spanning tree of G need not be a minimum spanning tree ofG Side note, not useful to this problem: There are algorithms that find a bottleneck spanning tree in O(n + e). Note that this is faster than the best MST algorithm. time 2. [15 pts] Let G=(V,E) be a directed graph with n vertices. A vertex r is a spigot if, for every v in V except for r, there is an edge from r to v, and there is no edge from v to r. Assuming that G is giver by its n by n adjacency matrix, give an O(n) algorithm to determine whether or not G has a spigot. has a s