The full cycle bound is reported open in the selected 2025 literature. Sharp results cover some degree parameters and symmetric graphs; the triangle and rainbow bounds have separate limitations.
Prove the sharp ceiling bound for all finite loopless simple digraphs and every positive integer degree parameter, without the restrictions or additive errors in the selected results.
Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
How to read this question
Minimum out-degree is a condition at every vertex
An average degree condition is weaker. A two-way pair of arcs already supplies a short cycle; the triangle question therefore uses oriented graphs.
Limit The precise assumptions on each statement determine which graph classes it covers.
Question paraphrased by OpenMath. Original wording is available in the sources.
Landscape
Figures and explorable examples. Selecting a statement opens its exact wording.
Where the cycle bound is proved
Each point (r, k) stands for digraphs with minimum out-degree r on n = kr vertices. For each r ≥ 6, the open part runs from the triangle case up to Shen’s curve, which rises with r. The triangle results are stated for oriented graphs; a digraph with opposite arcs already has a cycle of length two. Vertex-transitive digraphs, a class rather than a region, satisfy the bound for every r and n.
Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two.
Conjecture · Primary formulation
○Open
The full directed cycle bound
Must a simple directed graph with n vertices and minimum out-degree at least r ≥ 1 contain a directed cycle of length at most ⌈n/r⌉?
Assumptions
Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
In this problem
Finite directed graphs with no loops or parallel arcs; opposite arcs are allowed and already give a cycle of length two. Here n is the number of vertices and r is a positive integer lower bound on every vertex’s out-degree. The cycle visits distinct vertices, and ⌈n/r⌉ is rounded up.
The exact ceiling bound is known for r = 2, 3, 4, 5.
Blair D. Sullivan
Theorem · Special case
●ProvedBlair D. Sullivan
The sharp bound for out-degree two through five
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.
In this problem
The exact ceiling bound is known for r = 2, 3, 4, 5.
The degree parameter is restricted to two through five; the graph need not be regular.
Does not cover: This does not treat arbitrary degree parameters.
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.
In this problem
Vertex-transitive graphs satisfy the exact bound.
Vertex-transitivity requires the automorphism group to act transitively on vertices.
Does not cover: General digraphs need not have these symmetries.
Every finite loopless simple digraph with n vertices, minimum out-degree at least r ≥ 1 and n ≥ 2r² − 3r + 1 contains a directed cycle of length at most ⌈n/r⌉.
Assumptions
Shen’s theorem restricts the order relative to the minimum-degree parameter.
In this problem
The sharp bound holds when n ≥ 2r² − 3r + 1.
Shen’s theorem restricts the order relative to the minimum-degree parameter.
Does not cover: This leaves other ratios of graph order to degree untreated.
Handle an opposite-arc cycle first; otherwise forget directions and color each edge by its tail.
Hompe & Huynh 2025
Theorem · Conditional implication
●ProvedHompe & Huynh 2025
Why the rainbow conjecture would imply the directed bound
If Aharoni’s rainbow cycle conjecture holds for all n and r, then the Caccetta–Häggkvist directed cycle bound holds for all n and r.
Assumptions
Handle an opposite-arc cycle first; otherwise forget directions and color each edge by its tail. Distinct colors on a cycle force one outgoing edge at each cycle vertex.
In this problem
Handle an opposite-arc cycle first; otherwise forget directions and color each edge by its tail. Distinct colors on a cycle force one outgoing edge at each cycle vertex.
The rainbow generalization holds with an r-dependent additive error.
Hompe & Huynh 2025
Bound · Related result
●ProvedHompe & Huynh 2025
An additive bound for rainbow cycles
For every fixed integer r ≥ 1 there is a constant α_r, independent of n, such that every simple n-vertex edge-colored graph with n color classes of size at least r has a rainbow cycle of length at most n/r + α_r; the constants can be chosen with α_r = O(r⁵ log² r) as r grows.
Assumptions
The constant depends on r and is not removed by this theorem.
In this problem
The rainbow generalization holds with an r-dependent additive error.
The constant depends on r and is not removed by this theorem.
Does not cover: The result does not remove the error or prove the sharp directed bound.
A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Conjecture · Different statement · related variant
○Open
Aharoni’s rainbow cycle conjecture
Every simple undirected graph on n ≥ 1 vertices whose edges are partitioned into n color classes of size at least an integer r ≥ 1 contains a rainbow cycle of length at most ⌈n/r⌉.
Assumptions
A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
In this problem
A rainbow cycle uses pairwise distinct edge colors; this is a stronger conjecture in a different graph setting.
Reported in sources: No exact, source-pinned formal proof of the full conjecture was identified in this source selection. No OpenMath formalization task or execution is attached.
CComputation
None recorded
RReview
Not yet reviewed
OpenMath assessment: The full cycle bound is reported open in the selected 2025 literature. Sharp results cover some degree parameters and symmetric graphs; the triangle and rainbow bounds have separate limitations.
The canonical question and cited source selection only.
OpenMath pilot collection · OpenMath source curation · assessed Oct 12, 2026 · review due Jan 12, 2027
Collection last checked Oct 12, 2026.
Sources
Choose a starting point below. Each result links to its exact statement, cited passages and checks.