Course contentsShow
← Mathematics
Lesson 2679 of 3,12153. Graph TheoryFree lesson

Euler's Theorem for Eulerian Circuits

A connected graph has an Eulerian circuit if and only if every vertex has even degree.

Euler's Theorem for Eulerian Circuits

What You'll Learn

You'll discover the elegant condition that determines exactly when a connected graph contains an Eulerian circuit.

The Core Idea

Recall that an Eulerian circuit is a closed walk that traverses every edge of a graph exactly once, returning to the starting vertex. Euler's Theorem gives us a simple, beautiful test:

A connected graph has an Eulerian circuit if and only if every vertex has even degree.

This means two things:

  1. If every vertex in your connected graph has even degree, you're guaranteed to find an Eulerian circuit.
  2. Only if every vertex has even degree can such a circuit exist—even one vertex of odd degree makes it impossible.

Why Does This Work?

Think of it as an "in-and-out" balance. Every time you visit a vertex along your circuit, you use one edge to enter and another to exit. These come in pairs. Since the circuit closes (you return to the start), even your starting vertex has balanced entrances and exits. This pairing forces every vertex to have an even number of edges.

Example:

  • A square graph: all 4 vertices have degree 2 (even) → Eulerian circuit exists ✓
  • A triangle with one "tail" edge: one vertex has degree 3 (odd) → no Eulerian circuit ✗

This theorem is why the famous Königsberg bridge problem had no solution—two vertices had odd degree.

Why It Matters

Euler's Theorem transforms an exhausting search problem ("Can I trace this whole graph without lifting my pencil?") into a simple degree-counting check. It's foundational for routing, network design, and understanding graph structure.

Key Takeaway: A connected graph admits an Eulerian circuit if and only if all its vertices have even degree—pairing every entrance with an exit.