Exercise 5 (for week of Mar 22-26)


(A) A simple cycle in an undirected graph G=(V,E)
is a sequence of distinct vertices v_0,v_1,...,v_{k-1}, where 
k >= 3 and {v_0,v_1},{v_1,v_2}...{v_{k-1},v_0} are all in E.

(i) Show that if G has no cycles than m < n.
(ii) Explain how to use depth first search to determine in time O(n)
worst case time, whether G contains cycle.