Eulerian Circuits

Graph Theory · Axiom Academy

Understanding closed Eulerian trails and the conditions for their existence 1. Definition: Closed Eulerian Trail Eulerian Circuit: A trail that uses every edge exactly once and returns to its starting vertex (start = end). Unlike an Eulerian trail which may start and end at different vertices, an Eulerian circuit must form a closed loop . The starting and ending vertices must be the same. 2. Condition: All Vertices Have Even Degree For a connected graph to have an Eulerian circuit, there is a simple and elegant condition: Eulerian Circuit Theorem: A connected graph has an Eulerian circuit if and only if every vertex has even degree . This is more restrictive than the condition for Eulerian trails. Since we must return to the starting vertex, there can be no vertices of odd degree at all. 3. Every Eulerian Circuit is an Eulerian Trail Understanding the relationship between circuits and trails helps clarify these concepts: Since an Eulerian circuit satisfies all requirements of an Eulerian trail (uses every edge exactly once) plus the additional requirement that it returns to the start, we can say: When a graph has an Eulerian circuit, it typically has many different Eulerian circuits. Different starting points and different edge choices lead to different circuits. Start from any vertex (all have even degree) Choose different edges at each step

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