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
