The default requirements to be eligible for full credit are all of the following:

$($a$)$ Describe your algorithm clearly in English.

$($b$)$ Give pseudocode.

$($c$)$ Argue correctness, even if you don$$t give a formal proof and give a convincing

argument instead.

$($d$)$ Give with explanation the best upper bound that you can for the running time.

Q

uestion: An Eulerian tour in an undirected graph G is a cycle that is allowed to pass

through each vertex multiple times, but must use each edge exactly once.

$($a$)$ Show that G has an Eulerian tour if and only if all its vertices have even

degree.

Hint: Prove each direction separately. For the backward direction, use induction on the

number of vertices in G$.$

$($b$)$ We define an Eulerian path in an undirected graph as a path that uses every

edge exactly once. Similarly to part $($a$),$ can you give an if and only if characterization

of which undirected graphs have Eulerian paths? $($No proof required.$)$