Let G(V,E) be an undirected graph with n vertices and m edges such that G has two vertices s and t where the shortest path from s to t has length strictly more than n/2. Then, prove that there must be a vertex w ∈ V  {s,t} such that every path from s to t must pass through w. Furthermore, assuming that G is given to you in the adjacency-list representation along with vertices s and t, design an O(n + m) time algorithm to output such a vertex w. 4. Let G(V.E) be an undirected graph with n vertices and m edges such that G has two vertices s and t where the shortest path from s to t has length strictly more than n/2. Then, prove that there must be a vertex w e V{s,t} such that every path from s to t must pass through w. Furthermore, assuming that G is given to you in the adjacency-list representation along with vertices s and t, design an O(n + m) time algorithm to output such a vertex w. 

Answer rating: 100% (QA)

This is a challenging question that requires some mathematical reasoning and graph algorithms I will try to answer it as best as I can First let me prove that there must be a vertex w V st such that e... View the full answer