---
tag: 020422MDQF
kind: statement
role: theorem
name: Euler's theorem on Eulerian circuits
msc: [05C45]
uses: [0T0F6CCS9W, 0FFAYNMAJZ, 0NNYDD1AVR]
sources:
  - url: https://en.wikipedia.org/wiki/Eulerian_path
    locator: lead section
---

## Statement

Let $G$ be a finite [[connected|0FFAYNMAJZ]] [[graph|0JD5C82QMB]] or [[multigraph|01M5T0KDG7]] with at least one edge.
Then $G$ has an Eulerian circuit if and only if every vertex of $G$ has even [[degree|0T0F6CCS9W]].

## Remarks

The condition is necessary by the theorem on [[degrees along an Eulerian trail|0CDVDGWGEG]].
A consequence: a finite connected graph has an [[Eulerian trail|0NNYDD1AVR]] that is not closed if and only if exactly two vertices have odd degree.
Hierholzer's algorithm builds an Eulerian circuit: it joins closed trails until every edge is used.

## History

Leonhard Euler showed the necessity of the condition, and he stated without proof that it is sufficient.
The first complete proof is by Carl Hierholzer. It was published after his death, in 1873.

## Explanations

### L1 human

You can draw a connected graph in one closed stroke exactly when every vertex has an even number of edges.
Each time the pen passes a vertex, it uses one edge to arrive and one edge to leave.