Mathematics
Eulerian Paths and Circuits: Conditions for Traversable Graphs
Quick fact
A connected graph has an Eulerian circuit exactly when every vertex has an even degree, and an Eulerian trail exactly when exactly two vertices have odd degree—this is Euler's theorem, the foundation of graph theory.
Why this is interesting
Imagine trying to trace a shape without lifting your pen, crossing each line exactly once. Some figures are impossible—how can you know just by looking at the corners?
Read the full explanation
Understanding Eulerian Paths and Circuits: Conditions for Traversable Graphs
Think of a graph as a network of dots (vertices) connected by lines (edges). An Eulerian path uses every edge exactly once, and an Eulerian circuit is a path that also ends at the starting vertex. The key to whether such a path exists lies in the degree of each vertex—how many edges touch it. When you enter a vertex, you use one edge; to leave, you use another. So, in the middle of a path, each visit consumes a pair of edges. Therefore, all vertices except possibly the start and end must be 'balanced'—having an even degree. If you want a circuit, start and end are the same vertex, so every vertex must be even. If you allow a trail (not returning to start), you can have exactly two odd-degree vertices: the start and the end. This simple count is the whole secret!
A deeper explanation
Euler's theorem formalizes this intuition for connected graphs: a connected graph has an Eulerian circuit iff every vertex has even degree; it has an Eulerian trail (but not a circuit) iff exactly two vertices have odd degree. The proof is constructive. Necessity is clear: in a circuit, each visit to a vertex uses two edges (one in, one out), so total degree is twice the number of visits. For a trail, the start and end have odd degree, and all others even. Sufficiency is shown by an algorithm: start at an odd vertex (if present), follow edges, removing them, and whenever stuck, splice in cycles at visited vertices until all edges are used. Because every vertex has even degree, you never get stuck except at the start, guaranteeing a circuit. If exactly two odd vertices, start at one and finish at the other. This condition is remarkably easy to check, making it a powerful tool in network design and optimization problems like the Chinese Postman Problem, which seeks the shortest route covering every edge.