Showing that a graph has a cycle length less than something

2011-03-01T19:46:44Z

Hi guys, I have the following exercise to do but don't know how to approach it:

Let G be a graph with n nodes (n ≥ 2), and where every node has degree at least 3. Show that G has a cycle of length ≤ 2*ceiling (log n). And it allows me to consider a Breadth-First search tree.

First of all, what's the length of a cycle? Is it the number of arcs in the cycle? Secondly, how do I show it's 2*ceil(log n)?

Thanks, Sorin

Showing that a graph has a cycle length less than something - MathOverflow [closed]

Showing that a graph has a cycle length less than something