Minimum degree thresholds for even cycle residues
Dean's conjecture asserts that, for every integer $m\ge3$, every graph of minimum degree at least $m$ has a cycle whose length is divisible by $m$. This degree bound is best possible for odd $m$. For every integer $k\ge2$, we prove that every graph of minimum degree at least $2k-1$ has a cycle whose length is congruent to $r$ modulo $2k$ for every even $r\not\equiv2\pmod{2k}$. Consequently, $2k-1$ is the sharp minimum degree threshold for a cycle whose length is divisible by $2k$. For bipartite graphs, we prove that minimum degree at least $k$ guarantees the same residue classes for every $k\ge4$, and we characterize their end-blocks when no cycle has length congruent to $2$ modulo $2k$. The bipartite degree bound is also sharp, and the exclusion of residue $2$ is necessary even for connected graphs of arbitrarily large order.
Authors
- Shun‐ichi Maezawa (ORCID: https://orcid.org/0000-0003-1607-8665)
- Masaki Kashima (ORCID: https://orcid.org/0009-0006-8710-169X)
- Hojin Chu (ORCID: https://orcid.org/0000-0002-0484-9496)
- Boram Park
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.48550/arxiv.2611.22346
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint