Answer Happy

Problem 5. 25pts) [Remote Tenuous] Let G be a connected and undirected graph on n vertices and m edges. The distance d(u, v) between two vertices u and v in G is defined as the number of edges in a shortest path between the two vertices. The vertices u,v in G are said to: 1. form a remote pair if d(u, v) > 2. form a tenuous pair if there exists a vertex 1 $ {u, v} in G such that the graph G-2 obtained by deleting x from G contains no path between u and v. The main question has the following two parts: a. Give a modification of BFS algorithm that takes the adjacency list of graph G and a vertex u as the input, and outputs whether there exists a vertex v such that (u, v) forms a remote tenuous pair (that is, (u, v) is remote pair, as well as tenuous pair). Moreover, if there exists a v such that {u, v} is a remote tenuous pair, then the algorithm must output v and another vertex 1 ¢ {u, v} such that G-1 has no path between u and v. [15pts b. Prove the correctness of your algorithm, and show that it works in O(n+m) time. (10pts] a