Alphabeta MathEulerian and Hamiltonian Graphs
About this page
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.
✓ 16 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 16 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
2 · Logical flowchart
3 · Items
Definition
Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity
Definition
Directed walks, trails, paths and cycles, and strong connectivity
Definition
Euler trails and Euler circuits in multigraphs and digraphs
Lemma
In an even multigraph or balanced digraph, a trail maximal among unused incident edges returns to its start
Lemma
Edge-disjoint closed trails sharing a vertex can be spliced into one closed trail
Theorem
Euler's theorem and Hierholzer's construction: a connected finite undirected multigraph has an Euler circuit if and only if every degree is even
Corollary
A connected finite undirected multigraph has an Euler trail if and only if it has zero or two odd-degree vertices; an open Euler trail occurs exactly in the two-vertex case
Theorem
A finite digraph without isolated vertices has a directed Euler circuit if and only if it is weakly connected and every indegree equals the corresponding outdegree
Definition
Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs
Theorem
If G has a Hamilton cycle, then deleting any nonempty proper vertex set S leaves at most |S| connected components
Corollary
Every Hamiltonian graph on at least three vertices is 2-connected
Lemma
If nonadjacent u,v in an n-vertex graph satisfy deg(u)+deg(v)≥ n, then adding uv preserves Hamiltonicity in both directions
Definition
The Bondy-Chvatal closure of a finite simple graph
Lemma
The Bondy-Chvatal closure is independent of the order of eligible edge additions
Theorem
A graph is Hamiltonian if and only if its Bondy-Chvatal closure is Hamiltonian
Theorem
Ore's theorem: an n-vertex graph with n≥3 and deg(u)+deg(v)≥ n for every nonadjacent pair is Hamiltonian
Lemma
The minimum-degree condition δ(G)≥ n/2 implies Ore's degree-sum condition
Corollary
Dirac's theorem: every n-vertex graph with n≥3 and δ(G)≥ n/2 is Hamiltonian
Definition
A tournament is an orientation of a complete finite graph
Theorem
Redei's theorem: every nonempty tournament has a directed Hamilton path
Lemma
A tournament vertex having an in-neighbour and an out-neighbour on a directed cycle can be inserted into that cycle
Theorem