Math Conjectures

Caccetta–Häggkvist Conjecture

OPENLandmarkConjectureProposed 1978 · Standard version

Canonical statement

Let DD be a finite simple loopless digraph on nn vertices with minimum outdegree at least r≥1r\geq1. Then DD contains a directed cycle of length at most
⌈nr⌉. \left\lceil\frac nr\right\rceil.
View source LaTeX
Let \(D\) be a finite simple loopless digraph on \(n\)
vertices with minimum outdegree at least \(r\geq1\). Then \(D\) contains a
directed cycle of length at most
\[
  \left\lceil\frac nr\right\rceil.
\]
GRAPH-009:[CaccettaHaggkvist1978][FoxKeevashSudakov2010Directed][AharoniEtAl2023Nonuniform]
Graph theoryCombinatorics

Notes

Caccetta and Häggkvist conjectured in 1978 that a finite simple digraph on nn vertices in which every vertex has outdegree at least rr must contain a directed cycle of length at most ⌈n/r⌉\lceil n/r\rceil [CaccettaHaggkvist1978]. The most celebrated special case takes r=n/3r=n/3: every digraph with minimum outdegree at least n/3n/3 should contain a directed triangle, and even this case is open.

The conjecture has been established for several ranges of the ratio n/rn/r and for structured classes of digraphs, and approximate versions, in which the degree threshold or the cycle length is weakened by a constant, are well developed [FoxKeevashSudakov2010Directed]. The problem has also been extended in rainbow and nonuniform-degree directions, where analogues of the conjecture have been studied [AharoniEtAl2023Nonuniform].

The exact threshold ⌈n/r⌉\lceil n/r\rceil has resisted all approaches so far, and the conjecture remains open even in the directed-triangle case.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.