Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-02
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Euler's theorem and Hierholzer's construction: a connected finite undirected multigraph has an Euler circuit if and only if every degree is even

Statement

Let MM be a connected finite undirected multigraph. Then MM has an Euler circuit if and only if every vertex of MM has even degree. This includes the edgeless one-vertex multigraph, whose Euler circuit has length zero.

Facts & Assumptions

Given: A connected finite undirected multigraph MM.

[F1]

An Euler circuit is a closed trail using every edge exactly once (Euler trails and Euler circuits in multigraphs and digraphs).

[F2]

A loop contributes two to undirected degree, and connectivity is connectivity of the underlying simple graph (Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity).

[L1]

In an even finite multigraph, a nonempty trail that cannot be extended at its terminal vertex by an unused incident edge is closed (In an even multigraph or balanced digraph, a trail maximal among unused incident edges returns to its start).

[L2]

Edge-disjoint closed trails sharing a vertex can be spliced into one closed trail using their union (Edge-disjoint closed trails sharing a vertex can be spliced into one closed trail).

Proof

technique · direct
1.1

If MM has an Euler circuit, every arrival at a vertex is paired with a departure; a loop supplies both ends of such a pair. Because the circuit uses every edge, every degree is even.

F1F2algebra
1.2

Now suppose every degree is even. If MM has no edges, connectedness forces it to have one vertex, and the length-zero closed trail there is an Euler circuit.

givenF1F2
1.3

If MM has an edge, start with that edge and repeatedly extend the trail at its terminal vertex by any unused incident edge until no extension is possible. Finiteness makes this process stop, and [L1] makes the resulting nonempty trail CC closed.

givenL1
2.1

After deleting the edges of CC, every residual degree is even because a closed trail uses an even number of edge ends at each vertex. If an unused edge remains, connectedness of MM supplies an underlying path from a vertex of CC to that edge; at the first point where this path leaves the used-edge region, an unused edge is incident with a vertex of CC.

step 1.3F1F2algebra
3.1

Starting at that vertex, extend a trail using only residual edges until maximal. The residual degrees are even, so [L1] closes it, and [L2] splices it into CC.

step 2.1L1L2
4.1

Each splice strictly increases the number of used edges. Since MM has finitely many edges, repeating steps 2.1 and 3.1 terminates with one closed trail using every edge, hence an Euler circuit. Together with step 1.1 this proves both directions.

step 1.1step 1.2step 2.1step 3.1F1∎

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 21 results over 15 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources