# Selected topics in finite mathematics/Eulerian cycles

An Eulerian Cycle is a cycle in a graph which contains every edge.

## Objectives[edit | edit source]

Use every edge exactly once.

## Details[edit | edit source]

A graph is **connected** if there is a path between any two vertices.
If in a graph every vertex has an even number of edges incident upon it, the graph will have a Eulerian cycle.

A graph has an Eulerian Cycle if and only if all vertices have even numbers of edges. If a graph can't make an Eulerian Cycle, the process to make it a Eulerian Cycle is called Eulerizing.

A eulerian cycle is especially useful when trying to optimize paths and routes. For example, these cycles would be used when designing routes for trash collection, checking parking meters etc. Using a Eulerian cycle would allow one to save time by only walking down each street or pathway one time.

## Examples[edit | edit source]

- The graph given in figure E1 is an Eulerian graph. Its edges are labelled with an Eulerian Cycle: A-B-C-D-E-F-G-H-I-J-K

## Nonexamples[edit | edit source]

- In figure E1, A-B-C-I-H-K is not an Eulerian cycle because it misses an edge (several, in fact).

## FAQ[edit | edit source]

**Q:** How do you know where to place new edges when you are trying to Eulerize an graph?

**A:** Add edges to all the vertices with odd degree, until every vertex has even degree. There are multiple ways to Eulerize a graph, some will be more efficient than others.

## Homework[edit | edit source]

- Find an Eulerian cycle in the graph given in figure H1.