4. (20 points) Connectivity in undirected graphs vs. directed graphs (a) (10 points) Prove that in any connected undirected graph G (V, E) with |VI> 2, there are at least two vertices u, v E V whose removal (along with all the edges that touch them) leaves G still connected. Propose an efficient algorithm to find two such vertices. (Hint: The algorithm should be based on the proof or the proof should be based on the algorithm.) (b) (10 points) Give an example of a strongly connected directed graph G (V, E) such that for every v e V, removing v (along with all the edges that touches v) from G leaves a directed graph that is not strongly connected. Solution