Graphs with a cycle of length divisible by three (Q1322021)

Let \(G\) be a graph of order at least 2. It is shown that if \(G\) has at most one vertex of \(G\) of degree less than 3, then \(G\) has a cycle of length divisible by 3. As a consequence of this theorem, the following two conjectures (by Barefoot, Clark, Douthett and Entringer) are proved. (1) If \(G\) has order \(n\geq 3\) and size \(\geq 2n- 3\), then \(G\) has a cycle of length divisible by 3. (2) If \(\delta(G)\geq 3\) then \(G\) has a cycle of length divisible by 3. Furthermore, the following conjecture of Dean is shown to be true for \(m=3\): (3) If the connectivity of \(G\) satisfies \(\kappa(G)\geq m\geq 3\), then \(G\) contains a cycle of length \(0\text{ mod }m\).