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:

Bridges of Konigsberg

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 Eulerian circuit and that of an Eulerian path. 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 Seven Bridges 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. 

Solution: How to Tell if an Eulerian Path Exists