Suppose that $G = (V, E)$ is an undirected graph, and $G$ is promised not to contain $C_{k-1}$.Goal is to find any $C_k$ in $G$ using an efficient algorithm. Efficient, in this scope, meaning that finding all cycles and excluding all $C_{m>k}$ is out of question.First thing comes in mind is to use depth-first search, and return if a cycle is found. Since the problem is not finding all the $C_k$s, the algorithm should run approximately in $\mathcal{O}(|V| + |E|)$.Is this really lower bound, or do we need an algorithm that has higher asymptotic bound?
Efficient algorithm to find a $C_{k}$ in an undirected graph, that has no $C_{k-1}$
algorithms;graphs