This is a search problem that looks for a path that uses each edge exactly once where the path can be open or closed (tours).
There exists a path iff:
- Every vertex with the possible exception of two vertices (start and end) have an even degree
- The graph is connected
Note
The origin of graph theory is this and the Bridges of Konigsberg
Degrees
Note that the degree of a vertex is the number of edges that connects it
If these conditions are satisfied we can find a path:
Fleury’s Algorithm (1883)
- Start at any vertex (or the one with odd degree if it exists)
- Traverse an edge whose deletion does not disconnect the graph, unless you have no choice
- Delete the traverse edge and repeat