Proved
Established result in cited source ↗
AIM · Caccetta–Häggkvist workshop survey · §2.1, known cases; references [8], [22], [25] →
Observed Oct 12, 2026
Theorem · version 1
The sharp bound for out-degree two through five
Earlier version 1. View current version 2 →
Statement
For each r in {2, 3, 4, 5}, every finite loopless simple digraph with n vertices and minimum out-degree at least r contains a directed cycle of length at most ⌈n/r⌉.
Assumptions
- The degree parameter is restricted to two through five; the graph need not be regular.
Evidence
Source reports
Connections
In this problem · publication v8 · Selected context
Caccetta–Häggkvist cycle bound →
Special case · Proved
Scope: The exact ceiling bound is known for r = 2, 3, 4, 5.
Limit: This does not treat arbitrary degree parameters.
These results can cover the same graphs; their coverage is not added or expressed as a percentage.
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v9
Caccetta–Häggkvist cycle bound →
Special case · Proved
Scope: The exact ceiling bound is known for r = 2, 3, 4, 5.
Limit: This does not treat arbitrary degree parameters.
These results can cover the same graphs; their coverage is not added or expressed as a percentage.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
AIM · Caccetta–Häggkvist workshop survey →
- §2.1, known cases; references [8], [22], [25] → · Original passage ↗
Recorded wording
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist, Hamidoune and Hoang–Reed.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
- §2.1, vertex-transitive case → · Original passage ↗
Recorded wording
Vertex-transitive directed graphs satisfy the cycle bound, by Hamidoune’s connectivity argument.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
- §5, Theorem 5.1 → · Original passage ↗
Recorded wording
Shen’s theorem gives the sharp ceiling bound when the vertex count is at least 2r² − 3r + 1.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
Blair D. Sullivan; hosted by American Institute of Mathematics · Revision 2006-04-14
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established result in cited source ↗
Observed Oct 12, 2026 · Source passage →
Record details
- Claim ID
- claim-ch-small-outdegree
- Statement version
- 1
- SHA-256
- 676071f15728e513e591816e4b25d349c79a65e1d5870cd64005c1fb3f4841b7