Euler

The very first theorem of graph theory was presented in 1735 by Leonhard Euler.

The problem was known as the Seven Bridges of Königsberg.[80] The city of Königsberg, Prussia was set on the Pregel River, and included two large islands that were connected to each other and the mainland by seven bridges. The problem is to decide whether it is possible to follow a path that crosses each bridge exactly once and returns to the starting point. It is not possible: there is no Eulerian circuit.

In modern graph theory terms the trick is to determine if every node has the same in-degree as its out-degree. If they are equal, then every time the path reaches a node there must be an unused edge available to leave it.

Euler's insight allows an algorithm to be designed to find the Euler circuit, if it exists, that is almost trivial

ASSERT graph directed
ASSERT in-degree == out-degree for all vertices
SET vertex to first
WHILE true
    ADD vertex to circuit  
    FIND next vertex along unused edge
    MARK edge used
    IF no unused edge
        STOP

Pathfinder implements this algorithm, here is a screenshot

Performance Results, using the graphex application:

Node Count	Run Time ( secs )
1,000	0.02
10,000	0.2
100,000	15.0