How to find an Eulerian circuit in a complicated Graph

Question

Consider the following graph G:

(a) Give a decomposition of G into cycles.

(b) Find an Eulerian circuit in G.

This is a very complicated graph and each time I am trying to find the solution I am getting lost in the middle. Is there any technique to solve such a problem? Its really very difficult to find the Eulerian path.

Can anyone please help me?

Thanks in advance.

Answer 1

If a Eulerian circut exists, then you can start in any node and color any edge leaving it, then move to the node on the other side of the edge.

Upon arriving at a new node, color any other edge leaving the new node, and move along it.

Repeat the process until you

1. Are forced back to the starting node without covering all edges. In that case, you can expand your cycle because one of your nodes still has two outgoing edges. You can find an euler cycle on the unwalked edges starting and ending on that node.
2. You found an Euler cycle, in which case you are finished.