# 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

-
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? – joriki Mar 1 '11 at 21:17
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? – user7662 Mar 1 '11 at 21:59
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 :). – Srivatsan Sep 4 '11 at 22:54

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.

-
The tree cannot grow forever because then we'd have nodes with degree less than 3 and that breaks the specification. I see how I can get a cycle. But how should I explain the 2*ceil(log n) part? – user7662 Mar 1 '11 at 23:55
The tree cannot grow forever because you only have $n$ nodes. That's how you get the $\log n$ part. – Yuval Filmus Mar 2 '11 at 2:08
How does 'the tree cannot grow forever' fact lead to log n specifically? Also is there a way to represent this proof diagrammatically? – user7866 Mar 6 '11 at 15:47
We get the logarithm since a binary tree of height $h$ contains $2^{h+1}-1$ nodes. – Yuval Filmus Mar 6 '11 at 16:31

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.

-