Consider a graph such that each of the nodes has even degree. (a) Give an algorithm to decompose the graph into a collection of simple cycles that are disjoint, in the sense that they share no arcs (although they may share some nodes). (Here "decomposition" means that the union of the arcs of the component cycles is equal to the set of arcs of the graph.) Hint: Given a connected graph where each of the nodes has even degree, the deletion of the arcs of any cycle creates some connected subgraphs where each of the nodes has even degree (including possibly some isolated nodes).

(b) Assume in addition that the graph is connected. Show that there is an Euler cycle, i.e., a cycle that contains all the arcs of a graph exactly once. Hint: Apply the decomposition of part

(a) and successively merge an Euler cycle of a subgraph with a simple cycle.