Fleury's Algorithm and Euler's Paths and Cycles

On a graph, an Euler's path is a path that passes through all the edges of the graph, each edge exactly once. Euler's path which is a cycle is called Euler's cycle. For an Euler's path to exists, the graph must necessarily be connected, i.e. consists of a single connected component. Connectivity of the graph is a necessary but not a sufficient condition for the existence of an Euler path. For a connected graph, an Euler path exists if and only if the number of odd vertices is either 0 or 2; in the former case any Euler path is a cycle. In the latter case, the path starts at one and terminates at the other of the odd vertices.

Fleury's algorithm is a simple prescription for finding Euler paths and the applet below helps you master Fleury's algorithm. The instructions for using the applet are available on a separate page and can also be read under the first tab directly in the applet.

(This applet was created to accompany Excursions in Modern Mathematics, Seventh Edition, by Peter Tannenbaum © Pearson Education. Reproduced with permission.)

Fleury's algorithm works by simply constructing a path, starting at an arbitrary vertex (or at an odd one if there are any) and picking any of its incident edges, with a single caveat: any edge is permissible but those that leave the remaining graph disconnected. (For a connected graph, an edge whose removal affects the connectivity of the graph is called a bridge.)