Problem 5. (12 marks) Connectivity in undirected graphs vs. directed graphs.

a. (8 marks) Prove that in any connected undirected graph G = (V,E) with , there are at least two vertices 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. (4 marks) Give an example of a strongly connected directed graph G = (V,E) such that for every , removing v (along with all the edges that touches v) from G leaves a directed graph that is not strongly connected.