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.
$\endgroup$ 53 Answers
$\begingroup$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
- 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.
- You found an Euler cycle, in which case you are finished.
There are 8 vertices inside and 8 outside. Draw the 8 point star at the center first. Then go out and complete the octagon edges. Then zigzag in and out to finish the remaining edges.
$\endgroup$ 2 $\begingroup$I know this question was asked years ago, but I just came across it, while studying the subject:
(a) Give a decomposition of G into cycles.
Red Cycle: 9 - 12 - 15 - 10 - 13 - 16 - 11 - 14 - 9
Blue Cycle: 1 - 10 - 3 - 2 - 9 - 8 - 1
Green Cycle: 7 - 14 - 5 - 4 - 13 - 6 - 7
Pink Cycle: 1 - 2 - 11 - 4 - 3 - 12 - 5 - 6 - 15 - 8 - 7 - 16 - 1
(b) Find an Eulerian circuit in G.
1 - 10 - 3 - 2 - 9 - 12 - 15 - 10 - 13 - 16 - 11 - 14 - 9 - 8 - 1 - 2 - 11 - 4 - 3 - 12 - 5 - 6 - 15 - 8 - 7 - 14 - 5 - 4 - 13 - 6 - 7 - 16 - 1
It works!
(Reference )
