Proved
Established result in cited source ↗
AIM · Caccetta–Häggkvist workshop survey · §2.1, vertex-transitive case →
Observed Oct 21, 2026
Replaces an earlier source assessment. Version history ↓
Theorem · version 2
The sharp bound for vertex-transitive graphs
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 v11 · 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, Partial Results; references [5], [17], [19] → · Original passage ↗
Recorded wording
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist (r = 2), Hamidoune (r = 3) and Hoàng–Reed (r = 4, 5).
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-sha256-98251ac3
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 21, 2026 · Source passage →
Replaces an earlier source assessment; see the original source for its history.
Record details
- Claim ID
- claim-ch-vertex-transitive
- Statement version
- 2
- SHA-256
- ec36df3f2932e48a2a9fef9da20b46a0861df81f3a825b68fffccfccf49b594f