Consider the Chandra algorithm for finding a topological order: Start with the recursive DFS(v) procedure discussed in class and in the Brassard and Bratley book. Add a print[v] statement right after the visited(v) true statement at the beginning of the DFS(v). You should assume that the starting vertex is 1, and the neighbors of a vertex are examined in increasing numerical order (i.e. if there is a choice between two or more vertices, we pick the smaller one). Note that in this algorithm the list is not reversed at the end. You have to find a counterexample to show that the Chandra algorithm does not always work correctly:

(a) Show the graph G which is your counterexample.

(b) Show what order the vertices will be printed out by the Chandra algorithm.

(c) Show that this order is not a valid topological order.

(d) Show that there is a valid topological order on this graph.