# 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

## 2 Answers

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$.

-
for finding girth of a graph we need to run BFS for any vertex . then for this it has O(n^2) – Divuneh Apr 2 '12 at 12:02
You do not need to run BFS at any of the vertices that you already visited in a previous run. If you ran BFS at a vertex and found no circuit, you have found a connected component without circuit and you can ignore it for the rest of the algorithm. – Jesko Hüttenhain Apr 2 '12 at 12:22
And by ignoring it, I mean you can ignore the entire component, of course. – Jesko Hüttenhain Apr 2 '12 at 12:28
and if we have a cycle bigger than 19 , how can we ignor this component ? – Divuneh Apr 2 '12 at 12:36