Problem 1. Show that if a graph is connected and has n-1 edges, then it cannot contain a cycle. You may use the fact that if a graph is connected, then it must have at least n-1 edges.(Hint: Proof by contradiction).

Problem 2, You are trying to model a big (HUGE) joint family using a directed graph. You want to find the great-grandfather vertex, i.e., the member who has no outgoing edge to anyone and has incoming edges from everyone.

You have to find an algorithm to find such a vertex in the next three questions. Assume that you are given an arbitrary directed graph of n vertices as an adjacency matrix.
a. Can there be multiple great-grandfathers? Justify your answer very briefly.
b. Let us say, <1,2>, <1,3> are not edges but <1,4> is an edge. What can you say about the possibility of being great-grandfather for vertices 1,2,3,4?
c. After (b), let’s say you also come to know that <4,2>,<4,3> are edges, but <4,5> is not an edge. What can you say about the possibility of being great-grandfather for vertices 1,2,3,4,5?
d. Now derive a O(n) algorithm (using ideas obtained in questions (a) and (b)) for a general graph to find one great-grandfather vertex. It must be clear why your algorithm is correct (including a proof of correctness if required).

Problem 3 Recall the DFS algorithm.
a. If there is an edge from u ->  v, then f[u] > f[v] (f[x] denotes starting time for vertex x's visit).

b. Write an algorithm for Topological ordering based on the idea in (a). What is its running time (justify it)? It must be clear why your algorithm is correct (including a proof of correctness if required).

Problem 4: Write a program to find the strongly connected components in a digraph.

Problem 5: Let G = (V, E) be an undirected graph. Use depth-first search to design a linear algorithm to convert each edge in G to a directed edge such that the resulting graph is strongly connected, or determine that this is not possible.