6. Eulerian Paths
A path that runs through all edges.
1. Check Whether Connected
- Run DFS or BFS
- Start from any vertex with degree > 0
- Make sure all vertices with degree > 0 are reachable
2. Check Odd-Degree Vertices
| Odd-degree vertices | Result | Intuition |
|---|---|---|
| 0 | Eulerian cycle (and path) | We have to be able to leave every node that we enter |
| 2 | Eulerian path only | We can afford only leave (start node) and only enter (end node) two nodes |
| >2 | Neither | For some node which is neither start nor end, we get stuck because we have no edge to exit through left after entering. |
No node can have 1 odd-degree vertex because of the handshaking lemma: . Every edge counts toward the incident edges of two nodes.
Aside: In Directed Graphs
Conditions apply in slightly modified version:
- Graph must be connected if all edges where undirected
- At most one degree can be 1