4
$\begingroup$

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

Let $G$ be a graph with $n$ nodes ($n \ge 2$), and where every node has degree at least $3$. Show that $G$ has a cycle of length $\le 2\cdot \lceil\log n\rceil$. 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\cdot\lceil\log n\rceil$?

Thanks, Sorin

  • 1
    Yes, the length is the number of arcs. For the second part of the question, it might help to think about what would happen if you start at some node and look at all possible ways of moving away from it -- after how many steps would you necessarily be able to reach some node in more than one way, and what does that tell you about the length of the shortest cycle?2011-03-01
  • 0
    Can you give me an example of what you mean by "be able to reach some node in more than one way"? I drew a graph of 5 nodes, each with degree 3, except for the 4th one which has degree 4. The shortest cycle would have length 3, obviously. But then, how do I prove it for a general case?2011-03-01
  • 0
    Re "Is it the number of arcs in the cycle?" In any case, for a cycle, the number of arcs and the number of vertices are conveniently the same :).2011-09-04

2 Answers 2