# Cycle in Graph with $Δ(G)\leq 10$

I have a graph named $G$. degree of each node in $G$ is at most $10$. I need to find an algorithm to determine that this graph has any cycle with length less than $20$ with $O(n)$ .

I think it can solve with any theorem related to $Δ(G)$ and cycle in $G$ (but I'm not sure) .

I search it in google and stackoverflow , but I can't find any solution.

-
Is this homework? –  Louis Apr 2 '12 at 11:09
no. it's not homework. –  Divuneh Apr 2 '12 at 11:17
Re-tagged: graph refers to graphs of functions and not to discrete graphs - please, read the tag wiki when you tag. –  Ilya Apr 2 '12 at 11:32
thaks . I will read tag wiki next time. –  Divuneh Apr 2 '12 at 11:38
Your question in SO was very poor written, Also it doesn't show any effort, so It was not qualified for it, because of that removed, see my meta question about it. –  Saeed Apr 2 '12 at 23:10
show 1 more comment

There are $O(n)$ vertices in $G$, each of which can be an endpoint of at most $10^1+10^2+10^3+\cdots+10^{19}=O(1)$ walks of lengths between $1$ and $19$.

Hence, brute-force checking all of these $O(n)$ walks (e.g. via depth-first search or breadth-first search) will run in $O(n)$ time (albeit with a horribly large implicit constant).

-
The algorithm for finding a short cycle is BFS. The reason why this has runtime $\mathcal{O}(n)$ in your case is the degree bound on the vertices, which yields that $m\le 5n$.