The seven bridges puzzle
An Eulerian path walks a graph using every edge exactly once. If it also starts and ends at the same node, it is an Eulerian circuit. The puzzle of crossing each of seven bridges once, studied long ago, gave birth to graph theory and to a beautifully simple test.
The degree condition
Whether such a path exists depends only on node degrees, the number of edges touching each node.
- An Eulerian circuit exists when the graph is connected and every node has an even degree.
- An Eulerian path that is not a circuit exists when exactly two nodes have odd degree; the walk must start at one and finish at the other.
- With more than two odd degree nodes, no single trace covers all edges.
The reason is intuition itself: each time you pass through a node you use one edge to enter and one to leave, pairing them up, so interior nodes need even degree.
Building the path
Once the condition holds, a standard method repeatedly follows untouched edges, splicing in detours whenever it returns to a node with edges left, until all edges are consumed.
Key idea
An Eulerian path covering every edge once exists exactly when the graph is connected and has zero or two nodes of odd degree.