Hoàng-Reed Conjecture

Hoàng-Reed Conjecture

Definitions and mathematical statement

Let $D=(V,A)$ be a nonempty finite loopless simple digraph, allowing opposite arcs. Write $d^+(v)$ for the number of distinct vertices $w$ with $vw\in A$. A directed cycle is a subdigraph following a cyclic sequence of distinct vertices; cycles of length two are allowed when both opposite arcs occur.

For each integer $k\ge1$, the Hoàng--Reed conjecture asks whether the condition $d^+(v)\ge k$ for every vertex guarantees directed cycles $C_1,\ldots,C_k$ which can be ordered so that \[ \left|V(C_j)\cap\bigcup_{i=1}^{j-1}V(C_i)\right|\le1 \qquad(2\le j\le k). \] Thus each newly chosen cycle is either disjoint from all earlier cycles or meets their entire union at just one vertex. In particular the cycles are arc-disjoint. They are not required to be vertex-disjoint, and an arbitrarily large number of them may use one common vertex.

The condition is stronger than saying that every pair of cycles shares at most one vertex: a new cycle cannot meet two earlier cycles at two different vertices. The existence of a suitable ordering is part of the conclusion. Extra arcs of $D$ between vertices of the chosen cycles are ignored, since the union is not required to be induced.

For $k=1$ the assertion reduces to finding a directed cycle in a finite digraph with no sink. The general question seeks a structured collection of $k$ cycles from a local outdegree assumption, without any minimum indegree or connectivity requirement.

Short English statement

Does minimum outdegree k force k directed cycles that can be added one by one, each meeting all previous cycles in at most one vertex?

Research attempt: arc packing, overlap obstruction, and a girth reduction

Scope and literature check.

GPT-6 Astra Ultra, 2 October 2026. The intersection with the entire previous union, rather than each previous cycle separately, is the key quantifier. Welhan [S3] proved the Hoàng--Reed conjecture for minimum outdegree three, so older source discussions must not be read as a current claim that this case is unknown. The argument below is an independent elementary analysis of weaker packings and symmetric digraphs; it does not reprove that stronger published case. It also verifies exactly how the conjecture would imply the usual short-cycle bound.

1. Minimum outdegree always yields $k$ arc-disjoint cycles.

Every finite digraph with positive minimum outdegree contains a cycle: follow successive outgoing arcs until a vertex repeats, and extract a simple cycle. Delete its arcs. At any vertex, this deletion removes either one outgoing arc or none, so the remaining minimum outdegree is at least $k-1$. Repeating the operation $k$ times gives $k$ arc-disjoint directed cycles. Before step $i$, where counting starts at one, the remaining minimum outdegree is at least $k-i+1$, so each step is justified.

This proof controls arcs used at a vertex, but does not control how many vertices a later cycle shares with earlier cycles. Its output is therefore weaker than the required ordered intersection property. No minimum indegree hypothesis is needed for this weaker conclusion.

2. Pairwise small intersections do not repair the argument.

Consider the three directed triangles \[ (a,x,b,a),\qquad (b,y,c,b),\qquad (c,z,a,c). \] All six displayed vertices are distinct except for the repetitions explicitly indicating the triangle ends. The first and second triangles intersect at $b$, the second and third at $c$, and the first and third at $a$. They are arc-disjoint and every pair shares only one vertex. Nevertheless, in any ordering the last triangle meets the union of the first two in two distinct vertices. Thus this particular collection has no admissible ordering.

The example is an obstruction to upgrading a packing certificate, not a counterexample to the conjecture: the digraph consisting of these arcs does not satisfy minimum outdegree three. Keeping that hypothesis distinction is essential. It shows that even proving pairwise intersections at most one would leave a further step.

3. The symmetric subclass is immediate for every $k$.

Suppose every arc has its opposite and minimum outdegree is at least $k$. Choose a vertex $v$ and distinct outneighbours $w_1,\ldots,w_k$. The $k$ digons \[ v\to w_i\to v\qquad(1\le i\le k) \] are distinct and arc-disjoint. Each new one meets the earlier union exactly in $v$, so every ordering works. This proves the full desired intersection pattern on all symmetric digraphs, without a regularity or connectivity assumption. It relies on length-two cycles being allowed in the canonical convention; it would not apply to oriented graphs, where opposite arcs are absent.

4. Exact implication for the shortest cycle.

Let $g$ denote directed girth, the length of a shortest directed cycle. If the conjectured ordered collection exists, its first cycle has at least $g$ vertices, and every subsequent cycle contributes at least $g-1$ previously unused vertices. Therefore \[ n\ge g+(k-1)(g-1)=k(g-1)+1. \] Rearranging the integer inequality gives \[ g\le\left\lfloor\frac{n-1}{k}\right\rfloor+1 =\left\lceil\frac nk\right\rceil. \] This is precisely the Caccetta--Häggkvist short-cycle conclusion. The ceiling identity holds also when $k$ divides $n$, as follows by writing $n=qk+r$ with $0\le r<k$. Arc-disjointness alone would not give the vertex count; the stronger ordered overlap is what makes the implication work.

Verification and first remaining gap.

The script [S9] checks all six orders of the three-triangle example, constructs the symmetric digon certificates for $1\le k\le8$, and checks the displayed ceiling identity on bounded integer inputs. These computations accompany exact arguments. Deleting whole cycle vertex sets could enforce disjointness but may remove many outgoing neighbours at once. Deleting only cycle arcs preserves the inductive degree bound but loses the intersection condition. No intermediate deletion or exchange procedure overcoming both obstacles has been established here.

Final status.

UNRESOLVED for arbitrary digraphs. The symmetric subclass, the weaker arc-packing bound, and the precise short-cycle implication are proved.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3270 (OPG-47282), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Hoàng-Reed Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/hoand_reed_conjecture.
• S3 Manuel Welhan, The Hoàng--Reed Conjecture for $\delta^+=3$, Discrete Mathematics 310 $2010$, 1932--1939. https://doi.org/10.1016/j.disc.2010.03.001.
• S9 GPT-6 Astra Ultra, exact finite checks accompanying this attempt (2 October 2026). Repository script, Python standard library only. scripts/check_attempt_batch03_digraphs_2026_10_02.py.