- Eulerian Graphs

A graph that has an Euler circuit is called an Eulerian graph.## Euler's Theorem 1

- If a graph has any vertex of odd degree then it cannot have an euler circuit.
- If a graph is connected and every vertex is of even degree, then it at least has one euler circuit.

An applet on Finding Euler Circuits

## Euler's Theorem 2

- If a graph has more than two vertices of odd degree then it cannot have an euler path.
- If a graph is connected and has just two vertices of odd degree, then it at least has one euler path. Any such path must start at one of the odd-vertices and end at the other odd vertex.

## Fleury's Algorithm for finding an Euler Circuit

- Check to make sure that the graph is
**connected and all vertices are of even degree** - Start at any vertex
- Travel through an edge:

- If it is
**not a bridge for the untraveled part**, or - there is no other alternative

- If it is
- Label the edges in the order in which you travel them.
- When you cannot travel any more, stop. (You are done!)
An illustration of Fleury's Algorithm

## Eulerization of non-eulerian Graphs

Eulerization - If a graph has any vertex of odd degree then it cannot have an euler circuit.