Unlike our two previous corollaries, the lower bound in Corollary REF  does not get weaker with \(k\) .
This is because for all \(k>4\)  we can simply apply Theorem REF  with \(k=4\)  and then use known simple gadget reductions that show that \(k\) -cycle (detection or enumeration) for any \(k\)  is at least as hard as either the \(k=3\)  or \(k=4\)  case (see [1]}).The reduction simply subdivides some of the edges. Note that this trick is not useful in the hardness of approximation context because subdividing edges increases the distances even in the yes-case.
Either way, we separate \(k\) -cycle from the class \(\textsc {DelayC}_{lin}\)  of problems solvable with linear time preprocessing and constant delay [2]}.
This class has received significant attention in recent years from the enumeration algorithms community (see e.g. [3]}, [4]}, [5]}, [6]}).
Our result is somewhat surprising because enumerating all cycles (without restricting \(k\) ) is in the class \(\textsc {DelayC}_{lin}\)  [7]}.
