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

  • 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

5

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 <span class=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 <span class=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}$:

<span class=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.

3

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.

  • 0
    How does 'the tree cannot grow forever' fact lead to log$n$specifically? Also is there a way to represent this proof diagrammatically?2011-03-06