ProofAtlas

Extremal graph theory · directed cycles · connectivity

Caccetta–Häggkvist Conjecture

Collaboration beta

Must every finite loopless simple digraph with minimum outdegree d contain a directed cycle of length at most the ceiling of n divided by d?

δ+(G)≥d⇒g(G)≤⌈|V(G)|/d⌉
Listed inResearch Experiences in Graduate Studies open-problem entry
Known results and sources
A dark directed-cycle lattice surrounds a highlighted vertex with several outward arcs and a narrow return gate, suggesting the search for a short directed cycle without asserting that the open conjecture is proved.
The cover pairs minimum outward branching with the conjecture’s demand for a short directed return cycle.

Research problem

Exact mathematical statement

δ+(G)≥d⇒g(G)≤⌈|V(G)|d⌉.\delta^+(G)\ge d\quad\Longrightarrow\quad g(G)\le\left\lceil\frac{|V(G)|}{d}\right\rceil.

Equivalently, with n = |V(G)| and L = g(G) − 1, the conjecture says n ≥ dL + 1 for every finite loopless simple digraph.

Problem infographic

Problem at a glance

Scientific explainer for the open Caccetta–Häggkvist Conjecture. A finite loopless simple digraph surrounds a highlighted shortest directed cycle of length g, beside the exact question g ≤ ⌈n/d⌉ and a cyclic sharp-boundary family on ℤ/(dL+1)ℤ with arcs from i to i+1 through i+d.
The Caccetta–Häggkvist Conjecture asks whether minimum outdegree at least d forces a directed cycle of length at most ⌈n/d⌉. The cyclic family attains n = dL+1 and g = L+1, showing that the proposed bound is sharp.

Current mathematical picture

Where work on Caccetta–Häggkvist Conjecture stands

Open conjecture

The current work develops a minimal-counterexample and reverse-geometry program, closes the degree-two case, derives several degree-three normal forms, proves exact rank-one peeling under hereditary smaller-order validity, rules out multiple shortcuts, and isolates four current closing obligations. The conjecture remains open.

Strongest supported footholdCritical deletion and reverse spheres

Critical deletion forces minimum predecessors and exact reverse spheres.

Evidence posture · Reported result
Leading routeLength-weighted multigate composition

Generalize exact one-gate packet width, cut slack, and additive lifting toll to return rank k≥2.

Route status · Active route
Useful failureThin separator strategy

Regular counterexamples would have every proper separator larger than d/2, so small-bottleneck arguments cannot handle the core obstruction.

Route status · Eliminated route
Main reductionExact rank-one peeling

A rank-one channel peels with exact size and additive lifting toll.

Evidence posture · Reported reduction
Completed special caseDegree-two case completed

The return-fan dichotomy closes the conjectured bound for d=2.

Evidence posture · Reported special case
Priority open bridgeGeneralize exact peeling to k gates

Find a k≥2 analogue of width-d packet levels, common cut slack, and composable additive toll.

Task status · Ready to work on
Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Caccetta–Häggkvist Conjecture in numbers

2.2kretained lines of mathematical investigation2,173 in the current working snapshot
Argument development
1,797 · 83%
Explored or eliminated routes
145 · 7%
Computational analysis
13 · 1%
Open obligations
76 · 3%
Definitions and setup
142 · 7%
28selected mapped statements9routes investigated11reported milestones4open questions4contribution-ready tasks
How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byLouis Caccetta, Roland HäggkvistProposed1978Status checkedAug 2, 2026
Source recordedAug 2, 2026

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

17 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

17 selected steps

Scroll horizontally to explore the route

Working route overview for Caccetta–Häggkvist ConjectureA selected map of recorded claims, active routes, useful failures, open questions, and their explicit relationships. Search, filter, zoom, or pan within this page.Caccetta–Häggkvist conjecture — Depends on missing premiseCaccetta–HäggkvistconjectureExact rank-one peeling — Depends on missing premiseExact rank-one peelingTerminal U₂,₃ normal form — Depends on missing premiseTerminal U₂,₃ normal formTwo terminal degree-three return types — Depends on missing premiseTwo terminal degree-threereturn typesSmall two-gate blocks excluded — Depends on missing premiseSmall two-gate blocksexcludedDegree-three equality diamond — Depends on missing premiseDegree-three equalitydiamondExact reverse-layer defect identity — Depends on missing premiseExact reverse-layer defectidentityMaximal-defect clone reduction — Depends on missing premiseMaximal-defect clonereductionRoot-saturated clone core — Depends on missing premiseRoot-saturated clone coreTwo paths plus acyclic residue — Depends on missing premiseTwo paths plus acyclicresidueClosure rigidity — Depends on missing premiseClosure rigidityCritical deletion law — Depends on missing premiseCritical deletion lawLength-weighted multigate composition — activeLength-weighted multigatecompositionEliminate the terminal U₂,₃ core — OpenEliminate the terminal U₂,₃coreEliminate the terminal full fan — OpenEliminate the terminal fullfanProve additive two-reset accounting — OpenProve additive two-resetaccountingGeneralize exact peeling to k gates — OpenGeneralize exact peeling tok gates
Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeLength-weighted multigate composition

Generalize exact one-gate packet width, cut slack, and additive lifting toll to return rank k≥2.

Route status · Active route

Explored alternatives

Other routes

8 recorded
Route held in reserveStationary weighted reverse-distance

A circulation inequality would imply the conjecture, but may be strictly stronger and currently lacks a proof or counterexample.

Route status · Route held in reserve
Route held in reserveRegular return-distance charging

The exact identity isolates several terms, but no global charge is known.

Route status · Route held in reserve
Eliminated routeThin separator strategy

Regular counterexamples would have every proper separator larger than d/2, so small-bottleneck arguments cannot handle the core obstruction.

Route status · Eliminated route
Browse 5 more explored routes
Refuted routeFull return connectivity from minimum semidegree

Minimum in- and outdegree alone does not force an arc with d disjoint return paths.

Route status · Refuted route
Refuted routeLocal geodesic-window injection

Equality examples have missing and multiply hit ordered nonarcs, so any charge must be redistributed globally or fractionally.

Route status · Refuted route
Eliminated routeThreshold-trap induction

The degree-three trap is an acyclic-sink statement in disguise and adds no inductive force.

Route status · Eliminated route
Useful but insufficientOrdinary torso contraction

Ordinary quotient girth remembers only the largest channel loss; the desired bound needs additive reset costs or packet compensation.

Route status · Useful but insufficient
Not yet justifiedAssuming regularity

Trimming creates an outregular model, but saturation introduces excess degrees and no theorem regularizes the complete argument.

Route status · Not yet justified

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks
01
Generalize exact peeling to k gates

Find a k≥2 analogue of width-d packet levels, common cut slack, and composable additive toll.

Suggested move: Generalize the exact rank-one peeling theorem to multiple gates.
Ready to work on
02
Eliminate the terminal full fan

Classify non-path outgoing arcs using root saturation and the exact spanning partition.

Suggested move: Derive a contradiction internal to the equality core, without importing invalid original-edge provenance.
Ready to work on
03
Eliminate the terminal U₂,₃ core

Compare all three pair-linkages and their excess/residual budgets; force a third return, a short cycle, or a common dominator.

Suggested move: Seek a sum inequality showing that the three residual/excess budgets cannot coexist.
Ready to work on
04
Prove additive two-reset accounting

Derive |X|≥3L−q₁−q₂ from the two-root reset law, or close the complementary small-side branch.

Suggested move: Prove the additive reset inequality in the original degree-three branch.
Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 2, 2026
Current statusOpen conjecture

The general minimum-outdegree versus directed-girth conjecture remains open. The directed-triangle case is still the central unresolved case.

[8][12]
External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

  1. Peer reviewedHladký, Král', and Norin proved that minimum outdegree 0.3465n forces a directed triangle, versus the conjectured threshold n/3.[9]
  2. PreprintThe conjecture was proved for Cayley graphs and vertex-transitive graphs using additive-number-theoretic methods.[6]
  3. Peer reviewedHamidoune proved the original girth-order formulation for minimum outdegree three, extending the minimum-outdegree-two case proved by Caccetta and Häggkvist.[10]
14 cited sources3 related results or reductionsReferences

Mathematical neighborhood

Related results and reusable starting points

Current focusCaccetta-Häggkvist conjecture
Stronger or generalized formBehzad-Chartrand-Wall conjecture on regular digraphs of given girth

The 1970 regular-digraph girth problem is a precursor generalized by the minimum-outdegree formulation.

[11][4]
Solved special caseSeymour's second neighborhood conjecture

Seymour's conjecture would imply the directed-triangle case when both minimum indegree and outdegree are at least n/3.

[8]
Stronger or generalized formrainbow-cycle conjecture

Aharoni, Holzman, and DeVos formulate a rainbow-cycle generalization that implies the original conjecture.

[5]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

  • computation · source linked; not reproduced by ProofAtlasflag-algebra reproducibility example

    FlagSOS.jl documents a machine-readable constrained flag-algebra model for the triangle case and computes a basic upper bound; it is an exploratory/computational resource, not a proof of the conjecture.

    [14]
  • certificate · source linked; not reproduced by ProofAtlascomputer-assisted inequality certificate

    The 0.3465n theorem uses flag algebras and computer-generated inequalities; the arXiv record retains a CH.mw ancillary file.

    [3]

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

11 mapped milestonesretained argument map

Browse all 11 mapped stages

  1. stage 1Saturated minimal-counterexample model
  2. stage 2Critical deletion and reverse spheres
  3. stage 3One-gate branch excluded
  4. stage 4Degree-two case completed
  5. stage 5Degree-three return matroid identified
  6. stage 6Maximal-defect clone diamond
  7. stage 7Small two-gate blocks excluded
  8. stage 8Original bypass sharply constrained
  9. stage 9Root-saturated clone core
  10. stage 10Exact rank-one peeling
  11. stage 11Two terminal degree-three obstructions
Saturated minimal-counterexample modelThe current work reduces a hypothetical counterexample to a strongly connected saturated model with an exact reverse-distance rule.

Mapped research milestoneInitial research sequence

Research stage 1
Critical deletion and reverse spheresCritical deletion forces minimum predecessors, exact reverse spheres, and shortest-cycle coverage.

Mapped research milestoneInitial research sequence

Research stage 2
One-gate branch excludedThe current work rules out a single return gate at every minimum vertex.

Mapped research milestoneInitial research sequence

Research stage 3
Degree-two case completedThe current work gives a complete route-level proof of the conjectured bound for minimum outdegree two.

Mapped research milestoneInitial research sequence

Research stage 4
Degree-three return matroid identifiedThe current work forces the degree-three return matroid to be U₂,₃.

Mapped research milestoneInitial research sequence

Research stage 5
Maximal-defect clone diamondThe maximal-defect branch reduces to a smaller equality graph with an exact degree-three clone-diamond form.

Mapped research milestoneInitial research sequence

Research stage 6
Small two-gate blocks excludedThe current work rules out the two smallest large-side excesses and a shortest-cycle sink block.

Mapped research milestoneInitial research sequence

Research stage 7
Original bypass sharply constrainedProvenance eliminates the full fan in the original bypass and forces surviving branches before the halfway layer.

Mapped research milestoneInitial research sequence

Research stage 8
Root-saturated clone coreUnder hereditary smaller-order validity, the common predecessor can be chosen with an exact reverse sphere as its outneighborhood.

Mapped research milestoneInitial research sequence

Research stage 9
Exact rank-one peelingA rank-one channel peels with exact size dq+1 and an additive lifting toll.

Mapped research milestoneInitial research sequence

Research stage 10
Two terminal degree-three obstructionsAfter exact peeling, the degree-three program is reduced to a terminal full fan or U₂,₃ core, plus the separate multigate accounting problem.

Mapped research milestoneInitial research sequence

Research stage 11

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

27 standing statements1 proposed statements11 mathematical milestones4 open questions18 conditional results1 completed special cases
Statements by mathematical role28 selected mapped statements
  • theorem candidate1 of 281
  • lemma14 of 2814
  • equivalence1 of 281
  • negative result5 of 285
  • reduction7 of 287
Selected mathematical clusters7 mathematical clusters
Minimal counterexample and reverse geometrySaturation, deletion, reverse spheres, and defect identities.5 displayed rows
  • retained route statementExact saturation metricintermediate
  • retained route statementCritical deletion lawintermediate
  • retained route statementMinimum predecessors and reverse spheresintermediate
  • retained route statementLayer-bypass defect boundsintermediate
  • retained route statementExact reverse-layer defect identityintermediate
Return fans and gammoid structureOne-gate obstruction, degree-two closure, fan complement, and return matroid.5 displayed rows
  • retained route statementOne-gate branch excludedintermediate
  • retained route statementDegree-two case completedspecial case
  • retained route statementFan-complement degeneracyintermediate
  • retained route statementProper-dependency inequalityintermediate
  • retained route statementDegree-three return matroidconditional
Degree-three reductionsClone diamonds, return partitions, two-gate exclusions, and gate completeness.6 displayed rows
  • retained route statementMaximal-defect clone reductionconditional
  • retained route statementDegree-three equality diamondconditional
  • retained route statementFull return-fan partitionconditional
  • retained route statementTwo paths plus acyclic residueconditional
  • retained route statementSmall two-gate blocks excludedconditional
  • retained route statementQuantitative gate completenessconditional
Provenance-preserving maximal-defect bypassOriginal full-fan elimination and late-half constraints.2 displayed rows
  • retained route statementOriginal-bypass full fan eliminatedconditional
  • retained route statementLate-half branches excludedconditional
Root saturation and exact peelingRoot-saturated cores, exact rank-one peeling, and two terminal return types.6 displayed rows
  • retained route statementRoot-saturated clone coreconditional
  • retained route statementExact rank-one peelingconditional
  • retained route statementPacket levels and additive tollconditional
  • retained route statementSmall clone cores excludedconditional
  • retained route statementTwo terminal degree-three return typesconditional
  • retained route statementTerminal U₂,₃ normal formconditional
Secondary structural toolsCorrect packet tools that are not currently load-bearing.3 displayed rows
  • retained route statementPeriod compressionconditional
  • retained route statementMajority separatorsconditional
  • retained route statementClosure rigidityconditional
Open, paused, and eliminated routesThe live multigate program and the approaches whose exact limits are now understood.14 displayed rows · 9 routes included
  • Research targetEliminate the terminal U₂,₃ coreopen
  • Research targetEliminate the terminal full fanopen
  • Research targetProve additive two-reset accountingopen
  • Research targetGeneralize exact peeling to k gatesopen
  • ComputationAdversarial six-vertex step-{1,2} circulant for the local-window injection method.It satisfies equality in the unweighted return-distance identity but defeats literal local window injection. · reported unreproduced
  • Active routeLength-weighted multigate compositionGeneralize exact one-gate packet width, cut slack, and additive lifting toll to return rank k≥2.
  • Route held in reserveStationary weighted reverse-distanceA circulation inequality would imply the conjecture, but may be strictly stronger and currently lacks a proof or counterexample.
  • Route held in reserveRegular return-distance chargingThe exact identity isolates several terms, but no global charge is known.
  • Eliminated routeThin separator strategyRegular counterexamples would have every proper separator larger than d/2, so small-bottleneck arguments cannot handle the core obstruction.
  • Refuted routeFull return connectivity from minimum semidegreeMinimum in- and outdegree alone does not force an arc with d disjoint return paths.
  • Refuted routeLocal geodesic-window injectionEquality examples have missing and multiply hit ordered nonarcs, so any charge must be redistributed globally or fractionally.
  • Eliminated routeThreshold-trap inductionThe degree-three trap is an acyclic-sink statement in disguise and adds no inductive force.
  • Useful but insufficientOrdinary torso contractionOrdinary quotient girth remembers only the largest channel loss; the desired bound needs additive reset costs or packet compensation.
  • Not yet justifiedAssuming regularityTrimming creates an outregular model, but saturation introduces excess degrees and no theorem regularizes the complete argument.
How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeFind a k≥2 analogue of width-d packet levels, common cut slack, and composable additive toll.

The current research map records this as an open mathematical step.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

  • Establish a correct k-gate composition theorem with exact provenance and additive accounting.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable
Prepared starting pointGeneralize exact peeling to k gates

Caccetta–Häggkvist Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Must every finite loopless simple digraph with minimum outdegree d contain a directed cycle of length at most the ceiling of n divided by d?

  • Exact question and boundaries
  • Current routes and known obstacles
  • What a useful result should report
Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data
Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references14 cited works · next context review by Nov 2, 2026

The mathematical context was checked on Aug 2, 2026. Status can be refreshed sooner after a material result or claim.

  1. 1
    The Caccetta-Haggkvist conjecture — AIM workshop reportauthoritative webpage · accessed Aug 2, 2026
  2. 2
    On cycles through prescribed vertices in oriented graphsoriginal source · accessed Aug 2, 2026
  3. 3
    Counting flags in triangle-free digraphspreprint · accessed Aug 2, 2026
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
    On Seymour's and Sullivan's second neighbourhood conjecturespeer reviewed result · accessed Aug 2, 2026
  9. 9
    Counting flags in triangle-free digraphspeer reviewed result · accessed Aug 2, 2026
  10. 10
    A note on minimal directed graphs with given girthpeer reviewed result · accessed Aug 2, 2026
  11. 11
    On minimal regular digraphs with given girthpeer reviewed result · accessed Aug 2, 2026
  12. 12
    The Caccetta-Haggkvist Conjecture (REGS)authoritative webpage · accessed Aug 2, 2026
  13. 13
    Formal Conjectures repositoryformalization · accessed Aug 2, 2026
  14. 14
    Constrained example: Caccetta Haeggkvist conjectureauthoritative webpage · accessed Aug 2, 2026

Important qualifications

  • No authoritative public formalization was located in the scoped Formal Conjectures/Mathlib searches. An empty array is not a claim that none exists.
  • Empty formalization or computation lists mean that none was verified in this scoped search, not that none exists.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Expanded visual

Open original image