Problem 5 Given an undirected graph G = (V, E), the breadth-first-search starting at V EV (bf s() for short) is to generate a shortest path tree starting at vertex v EV. The diameter of G is the longest of all shortest paths 8(u, v), U, V EV. When G is a tree, the following algorithm is proposed to compute the diameter of G 1. Run bf (w), w EV, and compute the vertex 2 EV furthest from w. 2. Run bfs.) and compute the vertex y EV furthest from r. 3. Return (x, y) as the diameter of G. Prove that this algorithm is correct; i.e., 83, y) is in fact the longest among all the shortest paths between u, v EV. Problem 5 Given an undirected graph G = (V, E), the breadth-first-search starting at V EV (bf s() for short) is to generate a shortest path tree starting at vertex v EV. The diameter of G is the longest of all shortest paths 8(u, v), U, V EV. When G is a tree, the following algorithm is proposed to compute the diameter of G 1. Run bf (w), w EV, and compute the vertex 2 EV furthest from w. 2. Run bfs.) and compute the vertex y EV furthest from r. 3. Return (x, y) as the diameter of G. Prove that this algorithm is correct; i.e., 83, y) is in fact the longest among all the shortest paths between u, v EV