Question $4$:

$1.$ Say that a graph has an Euler Cycle $($a cycle that goes over all edges once$).$ Consider the vertices and edges of a leaf component $($a component with one separating vertex$).$ Show that the number of neighbors of the unique separating vertex in the leaf BCC is even.

$2.$ Show that if there is an Euler cycle for any BCC$,$ there is an Euler cycle in the graph.

Remarks: All the graphs are without self loops and parallel edges, and anti$-$parallel edges. In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.