Existence of cycles of length divisible by 3 3 or 4 4
Ilkyoo Choi, Hojin Chu, Ringi Kim, Boram Park · 2026
Read Existence of cycles of length divisible by 3 3 or 4 4 by Ilkyoo Choi, Hojin Chu, Ringi Kim, Boram Park (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-02731.txt.
Introduction
Ilkyoo Choi and three co-authors settle more of a graph theory question about cycles whose length divides evenly by a small number. A past conjecture held that any graph with high enough minimum degree has a cycle whose length is divisible by the degree bound. It is known true except in one open case. For lengths tied to three or four, stronger statements were already known.
The authors go further by characterizing all graphs above a degree floor, with few low-degree vertices, that avoid such cycles. From that full list, clean corollaries follow: with at most two degree-two vertices, a divisible-by-three cycle always exists. With at most three, and enough vertices, a divisible-by-four cycle exists. Characterizing the exceptions is stronger than just proving existence.
Catalog record
| CREATOR | Ilkyoo Choi, Hojin Chu, Ringi Kim, Boram Park |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.02731
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Existence of cycles of length divisible by 3 3 or 4 4 Ilkyoo Choi, Hojin Chu, Ringi Kim, Boram Park Abstract Dean conjectured that for each integer k ≥ 3 k\geq 3 , every graph with minimum degree at least k k has a cycle whose length is divisible by k k ; this conjecture is known to be true for all k ≠ 5 k\neq 5 . For k ∈ { 3 , 4 } k\in\{3,4\} , stronger statements are true: every graph with minimum degree at least 2 2 and at most k − 2 k-2 vertices of degree 2 2 has a cycle whose length is divisible by k k . We further strengthen these results by characterizing all graphs with minimum degree at least 2 2 and at most three vertices of degree 2 2 that have no cycle of length divisible by k k , for each k ∈ { 3 , 4 } k\in\{3,4\} . As a corollary, we obtain that every graph with minimum degree at least 2 2 and at most two vertices of degree 2 2 has a cycle whose length is divisible by 3, and that every graph on at least nine vertices with minimum degree at least 2 2 and at most three vertices of degree 2 2 has a cycle whose length is divisible by 4. 1 Introduction All graphs in this paper are finite and simple. Given a graph G and a vertex v , the degree and neighborhood of v are denoted by d_{G}(v) and N_{G}(v) , respectively. A d -vertex is a vertex of degree d . The set of 2 -vertices of a graph G is denoted by V_{2}(G) . For two integers k and \ell , an (\ell\bmod k) -cycle and an (\ell\bmod k) -path are a cycle and a path, respectively, of length m such that m\equiv\ell\pmod{k} ; they are also referred to as a cycle and a path, respectively, of length (\ell\bmod k) . The study of cycle lengths is a central theme in graph theory, with a long history of results related to the existence of cycles of prescribed lengths, see [ 3 , 27 ] . A fundamental line of research seeks to understand how structural conditions, such as large average degree [ 11 , 12 , 4 , 1 ] , large minimum degree [ 9 , 24 ] , large chromatic number [ 15 , 26 , 19 , 18 ] , or strong connectivity [ 5 , 8 , 13 ] , force the existence of cycles of prescribed lengths. A particularly well-studied direction concerns cycles whose lengths lie in prescribed congruence classes modulo an integer k . In particular, cycles whose lengths are divisible by k have attracted considerable attention. Early conjectures of Burr and Erdős [ 10 ] and work of Thomassen [ 23 ] suggest that sufficiently strong global conditions should guarantee the existence of cycles in all congruence classes modulo k , highlighting the fundamental role of extremal and minimum degree conditions in forcing such cycles, see, for example, [ 2 , 17 , 13 ] . While these problems aim to guarantee cycles in all congruence classes, it is natural to study existence of cycles in a single prescribed class. A classical direction in extremal graph theory is to relax underlying assumptions while still ensuring the existence of such cycles. For instance, see [ 25 , 22 , 6 ] . A natural starting point in this direction is the following conjecture of Dean [ 7 ] from 1988. Conjecture 1.1 (Dean’s conjecture) . For every integer k\geq 3 , every graph with minimum degree at least k contains a cycle of length divisible by k . The conjecture was verified for k\in\{3,4\} in [ 5 , 8 ] shortly after it was proposed, and more recently for all k\geq 6 [ 20 ] . In this paper, we dive deeper into the cases k=3 and k=4 . Notably, the known results for these values already hold under assumptions weaker than those in Dean’s conjecture, allowing a small number of 2 -vertices. Below are the results by Chen and Saito [ 5 ] and Dean, Lesniak, and Saito [ 8 ] establishing the cases k=3 and k=4 , respectively. Theorem 1.2 ( [ 5 ] ) . Every graph G with \delta(G)\geq 2 and |V_{2}(G)|\leq 1 contains a \mathrm{(}0\mathrm{\ mod\ 3)} -cycle. Theorem 1.3 ( [ 8 ] ) . Every graph G with \delta(G)\geq 2 and |V_{2}(G)|\leq 2 contains a \mathrm{(}0\mathrm{\ mod\ 4)} -cycle. These results naturally lead to the question of whether cycles of length divisible by 3 or 4 must still exist when more 2 -vertices are allowed. In this paper, we answer this question by completely characterizing graphs with minimum degree at least 2 and at most three 2 -vertices that have no cycle of length divisible by 3 (Theorem 1.4 ), and, separately, those that have no cycle of length divisible by 4 (Theorem 1.7 ). As a corollary, every graph with minimum degree at least 2 and at most two 2 -vertices has both a \mathrm{(}0\mathrm{\ mod\ 3)} -cycle and a \mathrm{(}0\mathrm{\ mod\ 4)} -cycle. Subsections 1.1 and 1.2 present our main results on \mathrm{(}0\mathrm{\ mod\ 3)} -cycles and \mathrm{(}0\mathrm{\ mod\ 4)} -cycles, respectively. 1.1 Graphs with a cycle of length divisible by 3 Our first main result characterizes all graphs with minimum degree at least 2 and at most three 2 -vertices that have no \mathrm{(}0\mathrm{\ mod\ 3)} -cycle. There are infinitely many such graphs, which we call exceptional graphs . We show that every exceptional graph can be generated from K_{2,3} by applying three operations, defined in Definition 1.6 . We now state our first main result. Theorem 1.4 . Let G be a graph with \delta(G)\geq 2 and |V_{2}(G)|\leq 3 . Then G has a \mathrm{(}0\mathrm{\ mod\ 3)} -cycle if and only if G is not an exceptional graph. Every exceptional graph has three 2 -vertices, so the following corollary is immediate; note that this corollary enlarges the class of graphs guaranteed to have a \mathrm{(}0\mathrm{\ mod\ 3)} -cycle by Theorem 1.2 . Corollary 1.5 . Let G be a graph with \delta(G)\geq 2 . If |V_{2}(G)|\leq 2 , then G has a \mathrm{(}0\mathrm{\ mod\ 3)} -cycle. We now define the class of exceptional graphs, a recursively constructed obstruction family obtained from K_{2,3} while preserving exactly three 2 -vertices; see Figure 1 for examples. Figure 1 : Some exceptional graphs with root r Definition 1.6 . Let r be a 2 -vertex of a graph G . We say G is an exceptional graph with root r if there exists a sequence (G_{0},x_{0},y_{0}),\ldots,(G_{n},x_{n},y_{n}) for some nonnegative integer n such that G_{0}=K_{2,3} , G_{n}=G , and for each i , the vertices r , x_{i} , and y_{i} are distinct 2 -vertices of G_{i} , and (1) if x_{i}y_{i}\not\in E(G_{i}) , then G_{i+1} is obtained from G_{i} by adding a path of length 3 joining x_{i} and y_{i} , (2) if x_{i}y_{i}\in E(G_{i}) , then G_{i+1} is obtained from G_{i} by adding either a new vertex v with N_{G_{i+1}}(v)=N_{G_{i}}(w) for some w\in\{x_{i},y_{i}\} or