# Graphs: Eulerian Paths and Circuits

## Revisting The Seven Bridges of Konigsberg

Recall our previous discussion of The Seven Bridges of Konigsberg problem, for which we are asked to determine if it is possible for a tourist to cross each bridge eactly once:

Recall further, that in our introduction to graphs, we discussed how Leonard Euler transformed the above image to the following abstract graph:

From this problem, Euler developed two important concepts for graph theory, that of an

**and that of an**

*Eulerian circuit***. We say that a graph has an Eulerian circuit if it is possible to traverse the graph and end up at the original vertex while having visited each edge exactly once. An Eulerian path is similar except that we need not end up on the same vertex that we started - the only requirement is that each edge is traversed exactly once. The**

*Eulerian path***problem, above, we want to know if an Eulerian path exists as we are not required to end up on the same vertex (land mass) from which we started.**

*Seven Bridges*