Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Challenge 3: the Caccetta–Häggkvist conjecture at parameter rrr

Definition
TenChallenges_Challenge_03

by utkuokur · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

caccetta-haggkvistdigraphsten-challenges

The scaled form of Challenge 3. For a natural number rrr, CH(r)\mathrm{CH}(r)CH(r) is the Caccetta–Häggkvist statement at minimum out-degree rrr:

if r≥1, every loopless digraph on n≥1 vertices with all out-degrees at least r has a directed cycle of length at most ⌈n/r⌉.\text{if } r\ge 1,\ \text{every loopless digraph on } n\ge 1 \text{ vertices with all out-degrees at least } r \text{ has a directed cycle of length at most } \lceil n/r\rceil.if r≥1, every loopless digraph on n≥1 vertices with all out-degrees at least r has a directed cycle of length at most ⌈n/r⌉.

It is the predicate CaccettaHaggkvistFor(r)\mathrm{CaccettaHaggkvistFor}(r)CaccettaHaggkvistFor(r) of the companion definition, unchanged. Known rungs are r≤5r\le 5r≤5; r=6r=6r=6 is open.

Definition code
import Definitions.Def_TenChallenges_CaccettaHaggkvist

namespace TenChallenges

/-- The Caccetta–Häggkvist conjecture at minimum out-degree `r`. -/
def statement_03 (r : ℕ) : Prop :=
  CaccettaHaggkvistFor r

end TenChallenges
Source
Ten Challenges repository, file Challenges/challenge_03.lean (commit ff14a56), https://github.com/TenChallenges/ten-challenges/blob/main/Challenges/challenge_03.lean; V. Bajpai, N. Bowler, J. Carmesin, U. Okur, 10 Scalable Challenges in Combinatorics, AI4Math @ CICM 2026, challenge 3.
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1

For every natural number rrr, the proposition statement⁡03(r)\operatorname{statement}_{03}(r)statement03​(r) is defined to be, with no change whatsoever, the proposition CH⁡(r)\operatorname{CH}(r)CH(r) (CaccettaHaggkvistFor r) from the imported file. Unfolded completely, statement⁡03(r)\operatorname{statement}_{03}(r)statement03​(r) asserts:

If 0<r0 < r0<r, then for every type VVV in the lowest type universe, every finiteness structure on VVV (so VVV is a finite type), every witness that VVV is nonempty, and every digraph GGG on VVV -- a digraph being merely a binary relation AdjG\mathrm{Adj}_GAdjG​ on VVV ("there is an arc from vvv to www") with no axioms -- the following holds. If

  1. for every vertex vvv, ¬ AdjG(v,v)\neg\, \mathrm{Adj}_G(v,v)¬AdjG​(v,v) (no loops), and
  2. for every vertex vvv,   r≤ncard⁡{ w∈V∣AdjG(v,w) }\; r \le \operatorname{ncard}\{\, w \in V \mid \mathrm{Adj}_G(v,w) \,\}r≤ncard{w∈V∣AdjG​(v,w)}, where ncard⁡\operatorname{ncard}ncard is the natural-number cardinality of a set (the number of elements of a finite set; junk value 000 for an infinite set, which cannot occur here because VVV is finite),

then there exists a natural number ℓ\ellℓ such that

2≤ℓ,ℓ⋅r<∣V∣+r,andHasCycle⁡G(ℓ),2 \le \ell, \qquad \ell \cdot r < |V| + r, \qquad \text{and} \qquad \operatorname{HasCycle}_G(\ell),2≤ℓ,ℓ⋅r<∣V∣+r,andHasCycleG​(ℓ),

where ∣V∣|V|∣V∣ is the number of elements of VVV, the arithmetic is on natural numbers (only multiplication and addition, no truncation), and HasCycle⁡G(ℓ)\operatorname{HasCycle}_G(\ell)HasCycleG​(ℓ) means: there is an injective map f:{0,…,ℓ−1}→Vf : \{0, \dots, \ell - 1\} \to Vf:{0,…,ℓ−1}→V (so f0,…,fℓ−1f_0, \dots, f_{\ell-1}f0​,…,fℓ−1​ are pairwise distinct) such that for every i∈{0,…,ℓ−1}i \in \{0, \dots, \ell-1\}i∈{0,…,ℓ−1} the arc AdjG(fi,fi+1 mod ℓ)\mathrm{Adj}_G(f_i, f_{i+1 \bmod \ell})AdjG​(fi​,fi+1modℓ​) is present; that is, ℓ\ellℓ distinct vertices v0→v1→⋯→vℓ−1→v0v_0 \to v_1 \to \cdots \to v_{\ell - 1} \to v_0v0​→v1​→⋯→vℓ−1​→v0​ joined by arcs in that direction, with nothing required about other arcs among them.

Edge cases carried over from the definition: statement⁡03(0)\operatorname{statement}_{03}(0)statement03​(0) is true unconditionally because 0<00 < 00<0 fails. For r≥1r \ge 1r≥1, the inequality ℓr<∣V∣+r\ell r < |V| + rℓr<∣V∣+r is equivalent to (ℓ−1)r<∣V∣(\ell - 1) r < |V|(ℓ−1)r<∣V∣, i.e. ℓ≤⌈∣V∣/r⌉\ell \le \lceil |V|/r \rceilℓ≤⌈∣V∣/r⌉. Looplessness bounds every out-degree by ∣V∣−1|V| - 1∣V∣−1, so when r≥∣V∣r \ge |V|r≥∣V∣ hypothesis 2 is unsatisfiable and the claim holds vacuously for that VVV. The clause 2≤ℓ2 \le \ell2≤ℓ excludes the length-000 "cycle" (which every digraph has vacuously) and the length-111 cycle (a loop); a length-222 cycle is a pair of distinct vertices with arcs in both directions. The digraph may contain, for distinct u,wu, wu,w, both arcs u→wu \to wu→w and w→uw \to uw→u; in-degrees are unconstrained.

Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by utkuokur · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me