Showing that a graph has a cycle length less than something 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
 A: The length of a cycle is the number of vertices in the cycle (which is equal to the number of edges in the cycle).  Some examples are given below:


Suppose we have a graph $G$ with $n \geq 2$ vertices and minimum degree $3$.  Let $C$ be the shortest cycle in $G$, and let $x$ be a vertex in $C$.  (Note: there exists at least one cycle in $G$, otherwise $G$ would be a forest, and non-empty forests have vertices of degree $0$ or $1$.)
Two slightly different situations can arise, depending on whether $C$ is an odd-length cycle or an even-length cycle.

Case I: $C$ is a $t$-cycle, where $t$ is odd.

To find the upper bound on $t$, we look at the neighbours of $x$, then their neighbours, and so on, until we first hit a cycle.  This will occur at depth $\frac{t-1}{2}$, since $t$ is odd.
The situations is as depicted below, where the cycle in bold represents $C$.

Every vertex on level $i \in \{1,2,\ldots,\frac{t-1}{2}-1\}$ is connected to at least $2$ vertices on level $i+1$ and exactly $1$ vertex on level $i-1$.  Any other situation would either imply (a) we have not accounted for all vertices at a given level or (b) there exists a cycle shorter than $C$.  Therefore
\begin{align*}
n &\geq 1+\sum_{i=0}^{\frac{t-1}{2}-1} 3 \cdot 2^i \\
  &=1+3 \cdot 2^{\frac{t-1}{2}} & \text{using the identity } \sum_{k=0}^a 2^a=2^{a+1}.
\end{align*}

Case II: $C$ is a $t$-cycle, where $t$ is even.

In this situation, the picture looks like the following:

And we can instead deduce
\begin{align*}
n &\geq 3+\sum_{i=0}^{\frac{t}{2}-2} 3 \cdot 2^i \\
  &=3+3 \cdot 2^{\frac{t}{2}-1} & \text{using the identity } \sum_{k=0}^a 2^a=2^{a+1}.
\end{align*}
Hence we have:

Lemma: $n > 2^{\frac{t}{2}}$ for all $n$.

Proof: If $t$ is odd, then $$n \geq 1+3 \cdot 2^{\frac{t-1}{2}} = 1+\frac{3}{\sqrt{2}} \cdot 2^{\frac{t}{2}} \geq 2^{\frac{t}{2}}.$$  If $t$ is even, then $$n \geq 3+3 \cdot 2^{\frac{t}{2}-1} = 3+\frac{3}{2} \cdot 2^{\frac{t}{2}} \geq 2^{\frac{t}{2}}.$$  [End of proof.]
So, if $t>2 \lceil \log_2 n \rceil$, then, by the lemma, we have $$n > 2^{\log_2 n} = n$$ giving a contradiction.  So finally, we can conclude:

Theorem: If $G$ is a graph with minimum degree $\geq 3$, then there exists a cycle of length at most $2 \lceil \log_2 n \rceil$.

It is worth noting that the bound can sometimes be achieved.  For example, this is $K_{3,3}$:

which has $n=6$ vertices and the shortest cycle is a $2 \lceil \log_2 n \rceil$-cycle.  It's not going to be "perfect" (since we rounded off in the lemma above), but it will be asymptotically the best possible.
A: Use your hint. Start "exploring" the graph from some vertex. As long as the edges you explore don't close a cycle, you'll get some tree - here you get to use the assumption on the degrees (what does it tell you about the tree?). The tree cannot grow forever (why?), and this is how you get your cycle.
