Graph Theory Basics - Main Theorem

Euler's Theorem characterizes which graphs admit Eulerian circuits, solving the original problem that founded graph theory.

DefinitionEuler's Theorem for Eulerian Circuits

Let $G$ be a connected graph. Then $G$ has an Eulerian circuit (a circuit using every edge exactly once) if and only if every vertex has even degree.

Proof:

Necessity ( $\Rightarrow$ ): If $G$ has an Eulerian circuit, then every vertex must have even degree.

Let $C$ be an Eulerian circuit. As we traverse $C$ , every time we visit a vertex $v$ , we enter via one edge and leave via another edge. These two edges contribute 2 to $\deg(v)$ .

Since $C$ uses every edge exactly once, each edge contributes exactly 1 to the degree count at each of its endpoints. Since edges are paired (entering and leaving) at each vertex during the traversal, $\deg(v)$ must be even for all $v$ .

Sufficiency ( $\Leftarrow$ ): If every vertex of connected $G$ has even degree, then $G$ has an Eulerian circuit.

We prove this by strong induction on the number of edges $m$ .

Base case: If $m = 0$ , the graph is a single vertex with an empty circuit (trivially Eulerian).

Inductive step: Assume the statement holds for all graphs with fewer than $m$ edges. Let $G$ have $m > 0$ edges with all vertices of even degree.

Step 1: Construct a cycle.

Start at any vertex $v_0$ and follow edges arbitrarily, never repeating an edge. Since every vertex has even degree, whenever we enter a vertex, there's always an unused edge to exit (except when we return to $v_0$ ).

Eventually, we must return to $v_0$ (since the graph is finite and we can't repeat edges). This forms a cycle $C$ .

Step 2: Remove $C$ and apply induction.

Remove all edges of $C$ from $G$ to get $G'$ . Every vertex in $G'$ still has even degree (we removed cycles, which contribute equally to entering/leaving).

The graph $G'$ may be disconnected, but each connected component $H_i$ has all vertices of even degree and fewer than $m$ edges. By the inductive hypothesis, each component $H_i$ has an Eulerian circuit $C_i$ .

Step 3: Splice circuits together.

As we traverse $C$ , whenever we encounter a vertex $v$ that belongs to some component $H_i$ of $G'$ , we can splice in the Eulerian circuit $C_i$ of $H_i$ at that point.

This produces an Eulerian circuit for $G$ , completing the proof. $\square$

ExampleApplication to Seven Bridges of Königsberg

The Seven Bridges of Königsberg problem asks whether one can walk through the city crossing each of its seven bridges exactly once.

Modeling this as a graph with landmasses as vertices and bridges as edges, we have 4 vertices with degrees: 3, 3, 3, 5 (all odd).

By Euler's theorem, no Eulerian path exists (we'd need at most 2 odd-degree vertices). Therefore, the desired walk is impossible.

Remark

For an Eulerian path (not necessarily a circuit), the condition is: the graph must have exactly 0 or 2 vertices of odd degree. If there are 0 odd-degree vertices, the path is actually a circuit. If there are exactly 2, the path must start at one odd-degree vertex and end at the other.

Eulerian circuits can be found in $O(|E|)$ time using Hierholzer's algorithm (1873): build a cycle, then recursively splice in cycles from any remaining edges. The Chinese Postman Problem asks for the shortest tour visiting every edge at least once (solved by finding minimum-weight matching on odd-degree vertices and adding duplicate edges).