Euler's Theorem

Graph Theory · Axiom Academy

Necessary and sufficient conditions for Eulerian circuits and trails in graphs 1. Definitions and Theorem Statement Eulerian Circuit: A closed walk in a graph that traverses every edge exactly once and returns to the starting vertex. Eulerian Trail: An open walk in a graph that traverses every edge exactly once, starting and ending at different vertices. Degree: The degree deg(v) of a vertex v is the number of edges incident to it. Let G be a finite, connected graph. Then: Part 1 (Eulerian Circuit): G has an Eulerian circuit if and only if every vertex has even degree. Part 2 (Eulerian Trail): G has an Eulerian trail if and only if G has exactly 0 or exactly 2 vertices of odd degree. 2. Eulerian Circuit: All Even Degrees For a connected graph to have an Eulerian circuit, every vertex must have even degree. Claim: If G has an Eulerian circuit, then every vertex has even degree. Proof: Suppose G has an Eulerian circuit C. As we traverse C, each time we visit a vertex v (other than the start/end), we use one edge to enter and one edge to leave. Since C uses every edge exactly once and returns to the starting vertex, each vertex must be entered and exited the same number of times. For the starting vertex, we leave once at the beginning and enter once at the end, plus any intermediate visits. Thus every vertex has degree = 2 × (number of visits), which is even. ∎ Proof of Sufficiency (⇐) - Sketch Claim: If every vertex has even degree, then G has an Eulerian circuit.

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