Dirac's Theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle, a cycle passing through every vertex exactly once, stating that this holds whenever the graph has at least three vertices and every vertex has degree at least half the total number of vertices. Named for Gabriel Andrew Dirac, it is one of the earliest and simplest sufficient conditions for Hamiltonicity, later generalized by Ore's Theorem and subsumed by the closure-based Bondy-Chvatal Theorem.
Facts
StatementA simple graph with n vertices (n >= 3) is Hamiltonian if every vertex has degree n/2 or greater. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Hamiltonian path (Wikipedia)
Sources
1. Dirac's theorem on Hamiltonian cycles, Wikipedia
Statement section
A simple graph with n vertices (n is greater than or equal to 3) is Hamiltonian if every vertex has degree n/2 or greater.
History section
Dirac's theorem on Hamiltonian cycles was proved in 1952 by Gabriel Andrew Dirac.
View the SourceHamiltonian path (Wikipedia)
In Branch: Graph Theory, Lead sentenceQuote, In Branch: Graph Theory, Lead sentence
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph tha
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.