a) Explain how a DFS can be used to look for cycles in a graph.
b) Explain why DFS trees cannot contain cross edges. (It may help to think about what it would mean if they did contain cross edges).
c) Prove that any connected graph G with n vertices and n-1 edges must be a tree.
(Hint: Use a proof by contradiction. Show that the assumption that G is not a tree, ie that G contains a cycle, will lead to the contradiction that G is not connected).