Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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? –  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
add comment

2 Answers

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.

share|improve this answer
    
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
add comment

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:

A 3-cycle, 4-cycle and a 5-cycle


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$.

The vertices at various distances from $x$ (odd case)

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:

The vertices at various distances from $x$ (even case)

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}$:

$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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.