Combinatorics · Conjecture

Caccetta–Häggkvist 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⌉?

Not assessedper AIM · Caccetta–Häggkvist workshop survey · checked Oct 1, 2026

Literature: 1 reference description
Formal: None linked
Computation: None recorded
Review: Not yet reviewed

Use with an agent

Earlier version 3 of this page. View current →

Overview

Known

The 2006 survey states a conjecture; this historical source does not establish its present status.

Precise statement

Finite simple directed graphs. This historical survey is a discovery source; the present research state has not been assessed.

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.

r ≥ 6 between the triangle case and Shen’s curver = 2, 3, 4, 5 for every nn ≥ 2r² − 3r + 1k ≤ 2.886, the triangle case at 0.3465nk = 3, the one-third triangle question

The open part: r ≥ 6 between the triangle case and Shen’s curve.
Proved for r = 2, 3, 4, 5 and every n.
Proved above the curve k = 2r − 3 + 1/r.
Proved for k ≤ 1/0.3465 ≈ 2.886 (oriented graphs).
The line k = 3, the one-third triangle question, is open.
Vertex-transitive graphs: proved for every r and n.

Dataset caccetta-haggkvist-regions v1 · Region boundaries from the cited statements: r ∈ {2, 3, 4, 5}; k = 2r − 3 + 1/r sampled exactly at r = 1.5, 2.0, …, 12.5 (from n ≥ 2r² − 3r + 1); k = 1/0.3465 (from minimum out-degree 0.3465n). No graphs are computed. Software: python 3.12.13. Exact rationals, stored as floating point. SHA-256 f28fbf73d57c… · Download JSON

Data

Layer	Status
Open: r ≥ 6 between the triangle case and Shen’s curve	open
Proved: r = 2, 3, 4, 5 for every n	proved
Proved: n ≥ 2r² − 3r + 1 (Shen)	proved
Proved: k ≤ 2.886, the triangle case at 0.3465n	proved
Open: k = 3, the one-third triangle question	open

Evidence

Evidence by kind
Literature	1 reference description Status per AIM · Caccetta–Häggkvist workshop survey · checked Oct 1, 2026. Not assessed: AIM · Caccetta–Häggkvist workshop survey · Conjecture 2.1; no current-status report ↗ · source dated Apr 14, 2006 · checked Oct 1, 2026The cited source item and version only; this is not an independent OpenMath assessment.
Formal	None linked
Computation	None recorded
Review	Not yet reviewed

Sources

Choose a starting point below. Each result links to its exact statement, cited passages and checks.

Start here

Introduction: Caccetta–Häggkvist cycle bound →

Bibliography 1

AIM · Caccetta–Häggkvist workshop survey →
Blair D. Sullivan; hosted by American Institute of Mathematics
Blair D. Sullivan, 14 April 2006, Conjecture 2.1 on page 2. Only a paraphrase and source link are published.

Selected literature; source observations and coverage limits are retained in the publication details.

Record details

Record version: 3
Classification: MSC2020 05C20 / 05C38
Prerequisite level: graduate

Source observations & version history →