Consider the graph given above. Add an edge so the resulting graph has an Euler trail (without repeating an existing edge).

Question

Now give an Euler trail through the graph with this new edge by listing the vertices in the order visited.

Answer 1

There can be at most two nodes of odd degree.