# 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.

What if applet does not run? |

(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*.)

- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles

|Activities| |Contact| |Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny64483099 |