Proved
Established result in cited source ↗
AIM · Caccetta–Häggkvist workshop survey · §2.1, vertex-transitive case →
Observed Oct 12, 2026
Theorem · version 1
The sharp bound for vertex-transitive graphs
Earlier version 1. View current version 2 →
Statement
Every finite loopless vertex-transitive simple digraph with n vertices and minimum out-degree at least r ≥ 1 contains a directed cycle of length at most ⌈n/r⌉.
Assumptions
- Vertex-transitivity requires the automorphism group to act transitively on vertices.
Evidence
Source reports
Connections
In this problem · publication v9 · Selected context
Caccetta–Häggkvist cycle bound →
Special case · Proved
Scope: Vertex-transitive graphs satisfy the exact bound.
Limit: General digraphs need not have these symmetries.
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, 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.
- §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.
- §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-vertex-transitive
- Statement version
- 1
- SHA-256
- ed40729480bcabc8366704fee81d9cd6e6eb59a04a313a8258238bb454de64cf