---
title: "Euler Tours: When They Exist"
summary: Euler's degree condition, why it is both necessary and sufficient, and the directed/undirected split.
difficulty: core
tags: [euler, cycles, existence]
prereq: [foundations/types, directed/definitions]
see: [euler/hierholzer, euler/debruijn]
---

An **Eulerian tour** is a closed walk using every edge exactly once; an **Eulerian trail** (or path) uses every edge exactly once but need not be closed. Graphs admitting them are called *Eulerian* / *semi-Eulerian*.

:::theorem title="Undirected"
A connected graph with at least one edge has
- an **Eulerian tour** $\iff$ every vertex has even degree,
- an **Eulerian trail** from $s$ to $t \ne s$ $\iff$ exactly $s$ and $t$ have odd degree.
("Connected" means: connected after ignoring isolated vertices.)
:::

:::proof
$(\Rightarrow)$ Each time a tour *passes through* $v$ it consumes one in-arrival and one departure, contributing 2 to $\deg(v)$; a closed tour starts and ends at the same vertex, so even the start vertex gets 2 per visit plus a final closing. Hence all degrees even. For an open trail, the two endpoints are entered/left one extra time each — exactly the odd ones.
$(\Leftarrow)$ Induct on $m$. All degrees even $\implies$ no vertex has degree 1, so some cycle $C$ exists (walk until you repeat). Remove $C$: every degree stays even, and each component of $G - C$ has fewer edges, so by induction each has an Euler tour. Splice: walk $C$, and whenever you enter a vertex of a component, detour along that component's tour and come back. All edges used exactly once. ∎
:::

:::theorem title="Directed"
A digraph has an Eulerian **circuit** $\iff$ (a) every vertex with nonzero degree lies in one strongly connected component of the underlying graph, and (b) $\deg^{+}(v) = \deg^{-}(v)$ for all $v$.
An Eulerian **path** $s \leadsto t$ exists $\iff$ $\deg^{+}(s) = \deg^{-}(s)+1$, $\deg^{-}(t) = \deg^{+}(t)+1$, all others balanced, plus the same connectivity condition.
:::

:::proof
Balance is necessary by the same pass-through argument (each visit uses one in-edge and one out-edge). For sufficiency, the balanced condition makes each weak component a union of directed cycles (take a maximal walk: it cannot get stuck except at the start, since every entry leaves an unused exit; so it closes). Then contract each cycle into one vertex — @proofs/contracting rule 1 — and repeat: the component structure and balance are preserved, so the cycle graph of the decomposition can be spliced back together. Connectivity (a) is what lets you splice at all. ∎
:::

:::note title="Why condition (a) is the one people forget"
Two disjoint directed cycles joined by a single arc $x \to y$: degrees are unbalanced, so (b) already fails. But four cycles arranged as two balanced pairs, each pair internally strongly connected and joined one-way, passes balance everywhere and still has no tour. Always test reachability on the *underlying* graph and, in the directed case, that all nonzero-degree vertices are in one SCC (@directed/scc).
:::

:::figure src="Konigsberg_Graph.svg" caption="Königsberg: degrees 5, 3, 3, 3 — four odd vertices, so neither a tour nor a trail exists. The whole subject starts from that one line of arithmetic."
:::

## Deciding, then counting
:::props title="Complexity of the Euler family"
- decide existence: $O(n + m)$ (degree scan + one DFS/SCC),
- construct: $O(n+m)$ with Hierholzer (@euler/hierholzer),
- **count** Euler tours: $\#P$-complete in general; for directed graphs the BEST theorem gives $\prod_v (\deg^{+}(v)-1)! \cdot \operatorname{ec}(G, r)$ where $\operatorname{ec}$ is the number of arborescences — an @matrices/matrix-tree determinant,
- minimum number of trails covering all edges of an undirected graph: $\max(1, \#\text{odd}/2)$ — one line, follows from the parity argument above.
:::

:::problems
- [[CSES 1691]] Mail Delivery | https://cses.fi/problemset/task/1691 | core | directed Euler circuit
- [[CSES 1693]] Teleporters Path | https://cses.fi/problemset/task/1693 | core | semi-Eulerian, directed
- [[CSES 2078]] Eulerian Subgraphs | https://cses.fi/problemset/task/2078 | hard | subset counting
:::