Dean's conjecture on cycles divisible by the minimum-degree bound

You can find the full proof (v1.0.1 as of Aug 31) here: https://zenodo.org/records/22182448

A brief summary of the proof is as follows:

Suppose for contradiction that $G$ is a finite simple graph with $\delta(G)\ge 5$ but contains no cycle whose length is divisible by $5$. Call a cycle $C$ with

$$|C|\equiv 0\pmod 5$$

a zero-cycle, and call a graph with no zero-cycle zero-free.

The proof first reduces an arbitrary zero-free counterexample to a much more rigid class of graphs called $5$-weak graphs. Starting from $G$, one passes to a $2$-connected subgraph $J$ in which all but possibly one vertex still have degree at least $5$. The structure of the $2$-cuts of such a zero-free graph is then analyzed. This forces $J$ to have one of two forms:

• Type I: $J$ is $3$-connected and all but possibly one vertex have degree at least $5$.
• Type II: $J$ has a unique degree-$2$ vertex $\theta$ with neighbors $u,v$, and replacing the path $u\theta v$ by the edge $uv$ produces a $3$-connected graph of minimum degree at least $5$.

Thus, if a counterexample exists, there is a zero-free $5$-weak graph $J$.

The rest of the proof establishes that no such graph can exist. Every $5$-weak graph falls into one of the three exhaustive cases

$$\boxed{\text{bipartite}} \qquad \boxed{\text{contains a triangle}} \qquad \boxed{\text{nonbipartite and triangle-free}}.$$

1. Bipartite case

Suppose $J$ is bipartite and zero-free. Since all cycles are even, the goal is to force an even cycle whose length is $0\pmod 5$.

The argument chooses a maximal structured subgraph built from $4$-cycles, called a tetragonal core, and studies how the rest of the graph can attach to it. Degree and connectivity conditions force many exterior attachments, while zero-freeness strongly restricts the possible lengths of paths through those attachments.

The possible tetragonal cores are eventually reduced to three small parameter cases. Each of these configurations is ruled out by a detailed structural analysis, so a zero-free bipartite $5$-weak graph cannot exist. Hence every bipartite $5$-weak graph contains a zero-cycle.

2. Graphs containing a triangle

Now suppose $J$ contains a triangle. Starting from a triangle, the proof grows a maximal trigonal core by repeatedly adding vertices along boundary edges.

A key feature of such a core is that a trigonal graph on $t$ vertices contains cycles of every length

$$3,4,\ldots,t.$$

Consequently, a sufficiently large trigonal core would automatically contain five consecutive cycle lengths, one of which must be divisible by $5$. Therefore, in a zero-free graph, a maximal trigonal core must be very small.

The remaining possibilities are a triangle itself or a $4$-vertex core, abstractly of the form $K_4-e$ or $K_4$. The high-degree and connectivity assumptions force enough paths outside the core to create several consecutive cycle lengths. Again, one of these lengths is $0\pmod 5$, contradicting zero-freeness.

Thus every $5$-weak graph containing a triangle contains a zero-cycle.

3. Nonbipartite, triangle-free case

This is the most involved case. Choose a shortest odd cycle $O$. Because $O$ is shortest, it is induced, and triangle-freeness severely restricts how vertices outside $O$ may attach to it.

The proof studies the components outside $O$, their attachment points on $O$, and the collection of paths they create between vertices of $O$. Combining these exterior paths with the two possible routes around $O$ produces cycles of many different residues modulo $5$. The degree and $3$-connectivity conditions guarantee that there are enough such attachments to force a zero-cycle.

The argument is carried out separately for the two forms of $5$-weak graphs:

• In Type I, the $3$-connected structure around a shortest odd cycle directly forces the required collection of cycle lengths.
• In Type II, write $H=J-\theta$. If $H$ is nonbipartite, the shortest-odd-cycle analysis applies again. If $H$ is bipartite, a separate structural argument produces a simple $u$--$v$ path $P$ with

$$|P|\equiv 3\pmod 5.$$

Adding the path $u\theta v$, which has length $2$, gives a cycle of length

$$|P|+2\equiv 3+2\equiv0\pmod5.$$

Hence every nonbipartite triangle-free $5$-weak graph also contains a zero-cycle.

Combining the three cases proves that every $5$-weak graph contains a zero-cycle. But the initial reduction says that any zero-free graph $G$ with $\delta(G)\ge5$ would contain a zero-free $5$-weak graph $J$. This is a contradiction.

Therefore every finite simple graph $G$ satisfying

$$\delta(G)\ge5$$

contains a cycle $C$ such that

$$|C|\equiv0\pmod5.$$

NOTE: This proof was developed with substantial use of LLMs, chiefly GPT 5.6 Sol, with Opus 5 and GLM 5.3 Flash as ancillary support. This proof has undergone multiple full-length adversarial audits, but has not yet been reviewed by an independent mathematician. This proof was authored by Elias Botsford.