Eulerian PathEdit
An Eulerian Path is a walk through a graph that uses every edge exactly once. This idea sits at the heart of graph theory, a field that studies networks of points connected by lines. The concept is named after Leonhard Euler, who in 1736 resolved a famous real-world puzzle about the Seven Bridges of Königsberg and, in doing so, laid the groundwork for a mathematical way of thinking about routes, connectivity, and optimization that underpins much of modern logistics and computing. In graph theory, a path that traverses every edge once and ends at a different vertex is often called an Eulerian path or Eulerian trail; a path that starts and ends at the same vertex is known as an Eulerian circuit.
The existence and construction of an Eulerian Path depend on the structure of the graph. In undirected graphs, the classical result is crisp: a finite connected graph has an Eulerian path if and only if it has exactly zero or two vertices of odd degree. If zero odd-degree vertices exist, the walk can start and end at the same vertex, forming a circuit. If exactly two vertices have odd degree, the path must start at one of the odd vertices and end at the other. In directed graphs, the condition involves indegree and outdegree: there must be either zero vertices where outdegree and indegree differ, yielding an Eulerian circuit, or there must be exactly one start vertex with outdegree = indegree + 1 and exactly one end vertex with indegree = outdegree + 1, with all other vertices balanced (indegree equals outdegree). Beyond these degree conditions, the graph must be connected in an appropriate sense (ignoring direction for the undirected view, or ensuring a form of strong connectivity when considering the directed edges). For a broad introduction to these ideas, see Graph theory and related treatments of degree and connectivity.
Formal definition
- An Eulerian Path in a finite graph is a trail that uses every edge exactly once. A trail is a walk with no repeated edges.
- In an undirected graph, a necessary and sufficient condition for the existence of an Eulerian Path is that the graph is connected (when restricted to vertices of nonzero degree) and has either zero or two vertices of odd degree. If zero odd-degree vertices occur, the Eulerian Path is a circuit.
- In a directed graph, a necessary and sufficient condition for an Eulerian Path is that either:
- every vertex has indegree equal to outdegree (Eulerian circuit exists, graph is connected in the directed sense after ignoring isolated vertices), or
- exactly one vertex has outdegree one greater than its indegree (the start) and exactly one vertex has indegree one greater than its outdegree (the end), with all other vertices balanced; the underlying undirected graph must be connected when considering vertices of nonzero degree.
These criteria connect to the classical reading of the Königsberg problem and generalize to modern network structures, where ensuring a single pass through every connection is a natural design goal. See also Degree (graph theory) for the precise notion of vertex degree and Strongly connected component for discussions of connectivity in directed graphs. For more on the global implications of these ideas in algorithmic contexts, examine Algorithm discussions surrounding path and circuit finding.
Existence criteria and remarks
- Undirected graphs:
- If a connected graph has exactly two odd-degree vertices, there is an Eulerian Path that starts at one odd vertex and ends at the other.
- If all vertices have even degree, there is an Eulerian Circuit (which is also an Eulerian Path).
- If more than two vertices have odd degree, no Eulerian Path exists that uses every edge exactly once.
- Directed graphs:
- If every vertex has equal indegree and outdegree and the graph is connected when ignoring edge directions, an Eulerian Circuit exists.
- If exactly one vertex has outdegree one greater than indegree (start) and exactly one vertex has indegree one greater than outdegree (end), with all others balanced, an Eulerian Path exists from the start to the end.
- If these balance conditions fail, an Eulerian Path does not exist that covers all edges.
The Königsberg problem historically illustrated the nonexistence of an Eulerian Path in a particular real-world layout, guiding later formalization. In contemporary practice, these criteria help engineers and computer scientists reason about route planning, circuit design, and data assembly tasks. For broader theory, see Graph theory and the study of degree and connectivity concepts such as Degree (graph theory) and Strongly connected component.
Algorithms
- Hierholzer's algorithm provides a robust method to construct an Eulerian Path or Circuit when it exists. It builds the path by following cycles and then stitching them together into a single route that covers every edge exactly once. This approach is efficient and widely used in practice; see Hierholzer's algorithm for a detailed treatment.
- Fleury's algorithm is another classical method that proceeds edge by edge, avoiding bridges unless no alternative exists. It is conceptually simple but can be less efficient in practice on large graphs, so Hierholzer’s approach is often preferred in large-scale applications. See Fleury's algorithm for more.
In directed graphs, the construction must respect the balance conditions on indegree and outdegree; adaptations of Hierholzer’s algorithm can handle these cases by following directed cycles and stitching them consistently. The algorithmic ideas behind Eulerian paths underpin techniques in data reconstruction and network design, including applications that use de Bruijn graphs to assemble sequences from short reads, a topic linked to de Bruijn graph and DNA sequencing.
Example and applications
A classic example is the Seven Bridges of Königsberg problem. The layout of landmasses and bridges makes it impossible to cross each bridge exactly once without retracing; this historical puzzle motivated Euler to formulate the condition on vertex degrees that governs the existence of an Eulerian Path. In smaller, simpler networks—such as a linear chain of four edges A—B—C—D with edges AB, BC, and CD—the graph has exactly two odd-degree vertices (A and D), so there exists an Eulerian Path from A to D.
Beyond pure theory, Eulerian paths have practical significance: - In genome assembly, de Bruijn graphs transform sequence reads into a structure where an Eulerian Path corresponds to a reconstructed genome sequence. See de Bruijn graph and DNA sequencing for the connection between combinatorial structure and biological data. - In logistics and maintenance planning, Eulerian paths model routes that cover every connection once, reducing redundant travel and improving efficiency. The underlying ideas align with broader graph-theoretic methods used in network optimization and route planning.