Eulerian Trails

Graph Theory · Axiom Academy

Understanding paths that traverse every edge exactly once in a graph 1. Definition and Basic Example Watch as we trace an Eulerian trail through a simple graph. Notice how we traverse each edge exactly once, starting at vertex A and ending at vertex D. 2. Eulerian Trail vs Eulerian Circuit It's important to distinguish between an Eulerian trail and an Eulerian circuit: The animation below shows both concepts side by side: The degree of a vertex is the number of edges incident to it. For an Eulerian trail to exist: 0 vertices of odd degree: The graph has an Eulerian circuit (also an Eulerian trail) 2 vertices of odd degree: The graph has an Eulerian trail starting at one odd-degree vertex and ending at the other More than 2 odd vertices: No Eulerian trail exists Watch as we check the degree of each vertex to determine if an Eulerian trail exists: To find an Eulerian trail in a graph: Check connectivity: Ensure all edges belong to a single connected component Count odd-degree vertices: There must be exactly 0 or 2 Choose starting vertex: If there are 2 odd-degree vertices, start at one of them Traverse the graph: Follow edges, marking each as used, until all edges are traversed Watch Hierholzer's algorithm find an Eulerian trail step by step:

This is the written version of the interactive lesson above. See the full Graph Theory course.