TOPICS
Search

Dean's Conjecture

Dean's conjecture (Dean 1991) asserts that, for every integer k>=3, every finite simple graph with minimum vertex degree at least k contains a cycle whose length is divisible by k. For odd integers k, the complete bipartite graphs K_(k-1,n) with n>=k-1 show that the minimum vertex degree cannot be decreased to k-1 (Luo et al. 2026).

The cases k=3 and k=4 were proved by Chen and Saito (1994) and Dean et al. (1993), respectively. Luo et al. (2026) proved the conjecture for all k>=6, leaving k=5 as the only unresolved case.

Botsford (2026b) claimed a proof for k=5. Version 1.0.1 supplies a complete two-case argument for the exceptional-leaf boundary-deletion step, covering whether the deletion witness lies on the shortest odd cycle or outside it. The revision changes no claimed result, computational predicate, or certificate output.

Nine finite configuration propositions in the proof were established by exhaustive search in a separate computational supplement (Botsford 2026a). VibeMathed (2026) replayed all 47 certificate runs successfully, but the reductions connecting arbitrary graphs to those finite configurations have not received independent verification. Botsford (2026b) credits GPT-5.6 Sol with the primary contribution to the proof, with additional assistance from Claude Opus 5 and GLM 5.3 Flash.

See also

Graph Cycle, Minimum Vertex Degree, Pancyclic Graph

Explore with Wolfram|Alpha

References

Botsford, E. "Computational Supplement for 'Cycles of Length Divisible by Five in Graphs of Minimum Degree Five'." 29 Aug 2026a. https://doi.org/10.5281/zenodo.22167084.Botsford, E. "Cycles of Length Divisible by Five in Graphs of Minimum Degree Five." 31 Aug 2026b. https://doi.org/10.5281/zenodo.22182448.Chen, G. T. and Saito, A. "Graphs with a Cycle of Length Divisible by Three." J. Combin. Th. Ser. B 60, 277-292, 1994. https://doi.org/10.1006/jctb.1994.1019.Dean, N. "Which Graphs Are Pancyclic Modulo k?" In Graph Theory, Combinatorics, and Applications, Vol. 1: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988 (Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk). New York: Wiley, pp. 315-326, 1991.Dean, N.; Lesniak, L.; and Saito, A. "Cycles of Length 0 Modulo 4 in Graphs." Disc. Math. 121, 37-49, 1993. https://doi.org/10.1016/0012-365X(93)90535-2.Luo, Y.; Ma, J.; and Zhao, Z. "Dean's Conjecture and Cycles Modulo k." 20 Jan 2026. https://arxiv.org/abs/2601.13552.VibeMathed. "Dean's Conjecture for k=5." 30 Aug 2026. https://vibemathed.com/problem/dean-s-conjecture-for-k-5.

Cite this as:

Weisstein, Eric W. "Dean's Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DeansConjecture.html

Subject classifications