Eulerian Trail

Worked Example

Consider an undirected graph with n = 4 vertices, structured like a square with a diagonal:

• Vertices: {0, 1, 2, 3}
• Edges: (0,1), (1,2), (2,3), (3,0), (0,2)

First, we check the degree of each vertex. The degrees are: vertex 0 has degree 3; vertex 1 has degree 2; vertex 2 has degree 3; vertex 3 has degree 2. Because exactly two vertices (0 and 2) have an odd degree, the graph contains an open Eulerian Trail, but not a Circuit.

Using Hierholzer's algorithm and prioritizing the smallest neighbor:

1. Start at the smallest odd vertex, 0. Push 0 to the stack.
2. From 0, the available neighbors are 1, 2, 3. We pick the smallest unused neighbor, 1. Stack: [0, 1].
3. From 1, the available neighbor is 2. Stack: [0, 1, 2].
4. From 2, the available neighbors are 0, 3. We pick 0. Stack: [0, 1, 2, 0].
5. From 0, the remaining unused neighbor is 3. Stack: [0, 1, 2, 0, 3].
6. From 3, the remaining unused neighbor is 2. Stack: [0, 1, 2, 0, 3, 2].
7. At vertex 2, there are no unused edges left. We pop the stack and append to the trail. Trail: [2].
8. We continue popping the stack since no more edges are available anywhere. The reverse pop list is [2, 3, 0, 2, 1, 0]. Reverse it to obtain the final trail [0, 1, 2, 0, 3, 2], starting at the chosen odd vertex 0.

Experiment

You can interactively run this algorithm in the Eulerian Trail module.

1. Set the Vertex count to 5.
2. Enter the following into the Edges textarea to form two connected triangles (0-1-2-0 and 0-3-4-0):
   0 1
   1 2
   0 2
   0 3
   3 4
   0 4
3. Click the Finish button.
4. Observe that the status shows Circuit, with 6 consumed edges. The final trace correctly shows the trail visiting all edges and returning to the start vertex.

Limitations

This interactive module bounds the maximum vertex count to 6 and maximum edge count to 10 lines to ensure deterministic layout within the bounded canvas and a readable bounded trace. Isolated vertices are ignored when checking connectivity of the edge support. With no edges we use trail [0], a convention rather than a nonempty edge traversal. Before completion the displayed pop list is partial and reversed, so it is not presented as the finished trail. It assumes simple undirected graphs; multigraphs (where multiple edges can exist between the same pair of vertices) and directed graphs (where Eulerian constraints differ based on in-degree and out-degree) are intentionally not supported in this implementation.

References

This material builds upon classical mathematical foundations and standard computer science algorithms for graph traversal and cycle detection. The explicit algorithm utilized within this module is closely aligned with Hierholzer's method, which provides an efficient procedure for finding an Eulerian circuit or trail in linear time relative to the number of edges. The following references offer a comprehensive formal proof and additional historical context regarding graph theory.

• Applied Discrete Structures: Section 9.4 - Traversals (Eulerian and Hamiltonian)