The minimum number of cycles of length $0$ modulo k in graphs with no proper k-coloring

Consider an integer k≥ 3. Toft and Tuza observed that every graph with no proper k-coloring has a cycle of length $0$ modulo k. Brewster, McGuinness, Moore, and Noel conjectured the following quantitative strengthening: every graph with no proper k-coloring has at least (k+1)!/2k cycles whose lengths are divisible by k. The conjecture is sharp, as demonstrated by the complete graph on $k+1$ vertices. Kim and Picollelli confirmed the conjecture for $k=3$. We establish the conjecture for every k≥ 3. In other words, we determine the minimum number of cycles of length $0$ modulo k in a graph with no proper k-coloring.