• Always leave one edge available to get back to the starting vertex as the last step.
• Don't use an edge to go to a vertex unless there is another edge available to leave that vertex (except for the last step).

However, there is an algorithm which, if followed, is guaranteed to produce an Euler circuit in a connected graph with no vertices of odd deGMATe:

Fleury’s algorithm (for a connected graph with no vertices of odd deGMATe):

1. Pick any vertex as a starting point.
2. Marking your path as you move from vertex to vertex, travel along any edges you wish except, DO NOT travel along an edge that is a bridge for the graph formed by the EDGES THAT HAVE YET TO BE TRAVELED-- unless you have to.
3. Continue until you return to your starting point.

THE PATH PRODUCED BY FLEURY’S ALGORITHM IS ALWAYS AN EULER CIRCUIT.

Exercise: Find an Euler Circuit for this graph.

Fleury’s Algorithm can be modified slightly to find Euler Paths when no Euler Circuits exist.
Remember this only happens for a connected graph with exactly 2 vertices of odd deGMATe.

Modification of Fleury’s Algorithm to find Euler Paths when no Euler Circuits exist
(for connected graphs with exactly 2 odd vertices).

Use Fleury’s Algorithm just as stated above EXCEPT always start at one of the odd vertices.

THE PATH PRODUCED BY THIS MODIFICATION OF FLEURY’S ALGORITHM IS ALWAYS AN EULER PATH.

Exercise: Find an Euler Path for this graph.

FINDING EULER CIRCUITS AND PATHS WITHOUT USING FLEURY'S ALGORITHM

Fleury's Algorithm (and its modification) is fine for programming a procedure for a computer to use to find Euler circuits and paths but usually people have no trouble finding Euler circuits without Fleury's Algorithm by just using a couple of commonsense guidelines:
•Always leave one edge available to get back to the starting vertex (for circuits) or to the other odd vertex (for paths) as the last step.
•Don't use an edge to go to a vertex unless there is another edge available to leave that vertex (except for the last step).

Back