An Eulierian cycle in a graph is a cycle (not necessarily simple) that uses every edge in the graph exactly one.

Show that a graph has an Eulerian cycle if and only if every vertex has even degree and all of the vertices with nonzero degree belong to the same connected component.

Design a linear-time algorithm to determine whether a graph has an Eulerian cycle, and if so, find one.