Existence of cycles of length divisible by 3 or 4

Abstract

Dean conjectured that for each integer $k\ge 3$, every graph with minimum degree at least $k$ has a cycle whose length is divisible by $k$; this conjecture is known to be true for all $k\ne 5$. For $k\in \{3,4\}$, stronger statements are true: every graph with minimum degree at least $2$ and at most $k-2$ vertices of degree $2$ has a cycle whose length is divisible by $k$. We further strengthen these results by characterizing all graphs with minimum degree at least $2$ and at most three vertices of degree $2$ that have no cycle of length divisible by $k$, for each $k\in \{3,4\}$. As a corollary, we obtain that every graph with minimum degree at least $2$ and at most two vertices of degree $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$ and at most three vertices of degree $2$ has a cycle whose length is divisible by $4$.