we-solve (beta)

Math-1120 · mathematics · Graph theory

Caccetta-Häggkvist Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $n\ge2$ and $1\le r\le n-1$ be integers. A simple digraph on $n$ vertices has no loops and has at most one arc for each ordered pair of distinct vertices; opposite arcs are permitted. Its minimum outdegree $\delta^+(D)$ is the smallest number of distinct outneighbours of a vertex. A directed cycle of length $\ell\ge2$ has $\ell$ distinct vertices and follows the arc directions around them; opposite arcs therefore constitute a cycle of length two.

The Caccetta--Häggkvist conjecture is \[ \delta^+(D)\ge r\quad\Longrightarrow\quad D\text{ has a directed cycle of length at most } \left\lceil\frac nr\right\rceil. \] The ceiling is the least integer at least $n/r$. The quantifiers cover every finite simple digraph satisfying the degree hypothesis. No indegree bound, regularity, or connectedness assumption is imposed. Because every vertex has an outgoing arc, following arcs eventually produces a cycle; the problem is the specific length guarantee.

For example, when $r\ge n/3$ the assertion asks for a cycle of length two or three. When the digraph is an orientation and hence has no 2-cycle, this becomes a directed-triangle assertion. The parameter $n$ counts vertices of the whole digraph and $r$ is a uniform lower bound, not an average degree. Replacing a cycle by a closed walk would weaken the formulation, although any shortest directed closed walk contains a simple directed cycle.

Short English statement

Does an n-vertex digraph of minimum outdegree r always contain a directed cycle of length at most the ceiling of n/r?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-1120-A2 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1120

Seymour second neighborhoods: The directed-cycle corollary obtains a directed triangle under BOTH minimum indegree and outdegree at least n/3, adding an indegree hypothesis to the recorded outdegree-only assertion.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Caccetta-Häggkvist Conjecture

OpenAI's claim

Seymour second neighborhoods: The paper claims that every finite nonempty oriented graph has a vertex whose second out-neighborhood is at least as large as its first. The second neighborhood excludes vertices already reachable in one step.

Mathematical statement of the claimed result

Mathematical claim 1.
For a nonempty finite oriented graph $D$, with no loops or oppositely directed pair of edges, let $N_1^+(v)$ be the out-neighbors and $N_2^+(v)$ the vertices at directed distance exactly two. The claimed theorem gives \[\exists v\in V(D):\quad|N_1^+(v)|\le|N_2^+(v)|.\] For triangle-free $D$ a corollary yields a vertex with $d^+(v)\le|Z(v)|$ and $n-1\ge2d^+(v)+d^-(v)$, where $Z(v)$ consists of non-neighbors excluding $v$. Hence $\delta^+\ge n/3$ and $\delta^-\ge n/3$ force a directed triangle; a digraph regular in both directions with degree $r$ and girth four has $n\ge3r+1$. These consequences require the specified in-degree conditions and do not give the full out-degree-only Caccetta--Häggkvist assertion.

Outline of the argument

Seymour second neighborhoods: A smallest counterexample is pruned to yield strict neighborhood inequalities for all proper vertex sets. Replacing vertices by transitive tournaments strengthens these to a discrete concavity inequality. Extremal families of ordered pairs and an augmented bipartite matching are then controlled by two factorizations of one matrix, contradicting that inequality.

Formal verification

Family 173 describes Lean coverage for the exact second-out-neighborhood inequality for a suitable vertex of every finite nonempty oriented graph.

Seymour second neighborhoods: The manuscript links SeymourSecondNeighborhood.lean (declaration OAI.SeymourSecondNeighborhood.exists_goodVertex).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →

Math-1120-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1120

Caccetta-Häggkvist Conjecture

Definitions and mathematical statement

Let $n\ge2$ and $1\le r\le n-1$ be integers. A simple digraph on $n$ vertices has no loops and has at most one arc for each ordered pair of distinct vertices; opposite arcs are permitted. Its minimum outdegree $\delta^+(D)$ is the smallest number of distinct outneighbours of a vertex. A directed cycle of length $\ell\ge2$ has $\ell$ distinct vertices and follows the arc directions around them; opposite arcs therefore constitute a cycle of length two.

The Caccetta--Häggkvist conjecture is \[ \delta^+(D)\ge r\quad\Longrightarrow\quad D\text{ has a directed cycle of length at most } \left\lceil\frac nr\right\rceil. \] The ceiling is the least integer at least $n/r$. The quantifiers cover every finite simple digraph satisfying the degree hypothesis. No indegree bound, regularity, or connectedness assumption is imposed. Because every vertex has an outgoing arc, following arcs eventually produces a cycle; the problem is the specific length guarantee.

For example, when $r\ge n/3$ the assertion asks for a cycle of length two or three. When the digraph is an orientation and hence has no 2-cycle, this becomes a directed-triangle assertion. The parameter $n$ counts vertices of the whole digraph and $r$ is a uniform lower bound, not an average degree. Replacing a cycle by a closed walk would weaken the formulation, although any shortest directed closed walk contains a simple directed cycle.

Short English statement

Does an n-vertex digraph of minimum outdegree r always contain a directed cycle of length at most the ceiling of n/r?

Research attempt: sharp circulants and limits of regularization

Scope and literature check.
GPT-6 Astra Ultra, 2 October 2026. Opposite arcs are allowed and count as a two-cycle. The hypothesis concerns minimum outdegree, not equal in- and outdegrees. Hoàng and Reed [S3] proved the conjecture for outdegree parameters four and five; Sullivan [S4] surveys the conjecture and several related problems. Those references are context, not a claim that their bounds represent the latest complete state of this large literature. The work here proves boundary cases, sharp examples for every parameter, and an explicit obstruction to a tempting reduction to regular digraphs.
1. Two directly provable regimes.
For $r=1$, repeatedly follow an outgoing arc. A repeated vertex produces a simple directed cycle of length at most $n$, exactly the required bound. For $r\ge n/2$, there are at least $nr$ arcs. If there were no opposite pair, there would be at most $n(n-1)/2<nr$ arcs. Thus a two-cycle exists. Since $r\le n-1$, the value $\lceil n/r\rceil$ in this regime is two, so this proves the target. These arguments include the smallest allowed orders and do not assume connectedness.
2. A valid reduction, followed by an invalid stronger one.
The condensation of a digraph into its strongly connected components is acyclic and has a sink component. All outgoing arcs of a vertex in that component stay inside it, so its induced digraph retains minimum outdegree at least $r$. If its order is $m\le n$, a cycle of length at most $\lceil m/r\rceil$ would suffice for the original problem. Thus it is enough to prove the conjecture for strongly connected digraphs.

Deleting excess outgoing arcs also reduces to exactly $r$ arcs leaving every vertex, without changing the vertex set. Such deletion need not preserve strong connectivity; applying the sink-component reduction again is legitimate. Neither operation guarantees equal indegrees. For example, on $\mathbb Z/5\mathbb Z$ start with arcs $x\to x+1,x+2$ and replace $0\to2$ by $0\to3$. The unit-step Hamilton cycle remains, so this digraph is strong and every outdegree is two, but its indegrees are $(2,2,1,3,2)$. It cannot have a spanning subdigraph with every indegree and outdegree two: retaining two outgoing arcs at each vertex forces retaining every arc. Therefore regularizing by arc deletion is not a valid general reduction.

3. Exact sharpness for every $(n,r)$.
Let $D_{n,r}$ have vertices $\mathbb Z/n\mathbb Z$ and arcs $x\to x+s$ for $1\le s\le r$. Its outdegree is exactly $r$. On a directed cycle of length $\ell$, select the step representative in $\{1,\ldots,r\}$ for each arc. Their sum is a positive multiple of $n$, so $\ell r\ge n$. Hence the directed girth is at least $\lceil n/r\rceil$.

Put $h=\lceil n/r\rceil$. The steps \[ \underbrace{r,\ldots,r}_{h-1\text{ times}}, n-(h-1)r \] all lie between one and $r$ and sum to $n$. Their proper partial sums lie strictly between zero and $n$, and are strictly increasing. They therefore define a simple directed $h$-cycle. The girth is exactly $h$. This verifies the ceiling and shows that any smaller universal target would be false, including when two-cycles occur.

4. Why counting an out-tree is insufficient.
High directed girth does not make different outgoing branches disjoint. In $D_{10,2}$, which has directed girth five, vertices zero and one both have vertex two as an outneighbour. A breadth-first exploration can merge without closing any short directed cycle. Thus multiplying the minimum outdegree at successive levels is not a justified vertex lower bound; a directed analogue of an undirected tree expansion cannot simply be assumed.
Verification, gap and final status.
The script [S9] computes shortest directed cycles for every $D_{n,r}$ with $2\le n\le30$ and $1\le r<n$, and verifies the strong, unbalanced example. The first remaining gap is controlling short cycles for arbitrary outregular digraphs when branches merge and indegrees vary. No regularity theorem or expansion estimate covering that gap is established. Full target: UNRESOLVED.

Sources

Go to contribution →