The Bermond-Thomassen Conjecture

The Bermond-Thomassen Conjecture

Definitions and mathematical statement

A finite simple digraph $D=(V,A)$ here has no loops and at most one arc for each ordered pair of distinct vertices. Both $uv$ and $vu$ are allowed. The outdegree $d^+(v)$ is the number of arcs with tail $v$, or equivalently the number of its distinct outneighbours. Set $\delta^+(D)=\min_{v\in V}d^+(v)$ for a nonempty digraph.

A directed cycle consists of distinct vertices $v_1,\ldots,v_m$ with $m\ge2$ and arcs $v_iv_{i+1}$, with indices taken modulo $m$. Thus two opposite arcs form an allowed cycle of length two. Cycles are vertex-disjoint if their vertex sets have empty pairwise intersection.

The Bermond--Thomassen conjecture is that for every integer $k\ge1$ and every such digraph, \[ \delta^+(D)\ge2k-1 \quad\Longrightarrow\quad D\text{ contains }k\text{ vertex-disjoint directed cycles}. \] No indegree condition and no strong-connectivity assumption are imposed. The cycles may have different lengths and need not cover all vertices.

The threshold cannot be lowered to $2k-2$: the complete symmetric digraph on $2k-1$ vertices has this outdegree and every directed cycle uses at least two vertices, precluding $k$ vertex-disjoint cycles. Here "symmetric" means that each pair of vertices has both possible arcs. This example also explains why confusing vertex disjointness with arc disjointness would change the sharp question.

Short English statement

Does minimum outdegree at least 2k−1 force k vertex-disjoint directed cycles?

Research attempt

Scope and process.

This is a GPT-6 Astra Ultra research attempt dated 2 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.

Current source check and conventions.

The August 2026 paper of Bessy, Muis, Sereni, Steiner and Wiederrecht [R1] explicitly records that the conjecture remains unresolved for $k\ge4$. It proves a relaxation in which each packed cycle may instead become directed after reversing one arc. Such a cycle is not necessarily a directed cycle of the original digraph, so that theorem is not a solution of the present target. Here cycles of length two are permitted and disjointness always means vertex disjointness.

The first case and a symmetric restricted theorem.

If every vertex has an outgoing neighbour, start at any vertex and repeatedly follow an outgoing arc. Finiteness forces a repeated vertex; the portion between its first and next occurrence contains a directed cycle. Thus the assertion for $k=1$ follows without any indegree or connectivity assumption.

Now assume the digraph is symmetric: every arc has its reverse. Its underlying graph has minimum degree at least $2k-1$. We claim it has a matching of size at least $k$. Otherwise take a maximum matching with at most $k-1$ edges. Its covered set has at most $2k-2$ vertices. Minimum degree implies the graph has at least $2k$ vertices, so choose an uncovered vertex $v$. Maximality of the matching implies that every neighbour of $v$ is covered, since an edge to another uncovered vertex could be added. This gives $d(v)\le2k-2$, a contradiction. Replacing the $k$ matching edges by their two opposite arcs produces $k$ vertex-disjoint directed 2-cycles. This proves the target for every symmetric digraph, not only for complete ones.

The canonical example on $2k-1$ vertices shows sharpness within this class. Conversely, on exactly $2k$ vertices the required outdegree forces every possible arc, so the assertion holds there as well. The availability of opposite arcs is useful here and must not be silently removed from the problem.

A bound with an explicit cycle-length parameter.

Suppose, more generally, that every directed cycle has length at most $L$, where $L\ge2$, and write $\delta=\delta^+(D)\ge1$. Take a maximal family of $r$ vertex-disjoint directed cycles and let $U$ be their union. Then $|U|\le Lr$. The induced digraph on the remaining vertices is acyclic, since another cycle would extend the family. If it is nonempty, it has a vertex with no outgoing arc to another remaining vertex: follow outgoing arcs within it to prove this, or else a cycle would result. All original outgoing neighbours of that vertex lie in $U$, so $\delta\le |U|\le Lr$. If no vertices remain, then $\delta\le |V(D)|-1<Lr$ instead. Therefore \[ r\ge\left\lceil\frac{\delta}{L}\right\rceil. \] In particular, $\delta\ge L(k-1)+1$ guarantees $k$ disjoint cycles under this extra circumference bound. For $L=2$ this gives exactly $2k-1$, but the conjecture imposes no such bound on cycle lengths.

Why deleting a shortest cycle does not finish the proof.

An induction at the proposed threshold would be immediate if one could always delete a directed 2-cycle: removing its two vertices lowers every remaining outdegree by at most two. There need not be any such cycle. On $\mathbb Z/7\mathbb Z$, orient $i$ toward $i+1,i+2,i+3$. Each vertex has outdegree three and there are no opposite arcs, so this meets the $k=2$ threshold without a 2-cycle. It does have disjoint directed triangles $(0,1,4)$ and $(2,3,6)$. Thus the obstruction defeats this induction rule, not the conjecture. The exact checks in [R2] verify those arcs, degrees and disjointness. They also verify the complete symmetric sharpness examples for small $k$; the matching proof is what covers arbitrary orders.

Final status and first remaining gap.

UNRESOLVED. The symmetric case and a circumference-dependent packing bound are proved. For general nonsymmetric digraphs, the maximal-packing argument loses a factor equal to the possible cycle length. There is no mechanism here replacing that loss by two while retaining enough outdegree; that is the first missing step toward the full threshold for $k\ge4$.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3257 (OPG-611), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, The Bermond-Thomassen Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/the_bermond_thomassen_conjecture.

• R1 Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni, Raphael Steiner and Sebastian Wiederrecht, A relaxation of the Bermond--Thomassen conjecture, submitted 13 August 2026. Primary abstract checked 2 October 2026. https://arxiv.org/abs/2608.12948.
• R2 Reproducible finite checks: scripts/check_attempt_batch03_colouring_2026_10_02.py, section 3257.