Finding a cycle of length log(n) given min degree

Question

Let $G = (V, E)$ be an undirected graph such that every $v\in V$ has $\deg(v) \geq 3$. We must create an algorithm that outputs a cycle of length O(log(n)) if it exists. This algorithm must return in linear time. If such a cycle exists return True, if it doesn't return False.

I had a couple ideas of where to start, but didn't really have a good way to tie them together. My first idea was construction of this graph. Since it has at least degree of 3 I noticed it can always be in a tree-like structure like so:

it can extends further down. It is shaped like this because of the minimum degree 3 requirement. If we inspect the length for the tree we can see the distance is $\log{n}$ edges of height.

After this we could maybe run an algorithm for cycle finding?? I'm just looking for ideas of how to do this problem in linear time in a clean and concise way, any help would be great.

Answer 1

Assume that the graph is non-empty, pick an arbitrary vertex $s$ and construct the first $\lceil \log n \rceil$ levels of the BFS tree $T$ from $s$.

You will encounter some non-tree edge $(u,v)$ in the process. This is trivially true when $n=4$, as the only possible graph that satisfies the degree constraints is $K_4$ (the case $1 \le n \le 3$ is impossible), therefore we assume $n \ge 5$. If no non-tree edge is encountered, then the number of vertices in the first $\lceil \log n \rceil$ levels of the tree must be at least $1 + 3 \cdot \sum_{i=0}^{\lceil \log n \rceil -2} \ge 1 + 3 (2^{\log n - 1} -1) = 1+ \frac{3}{2}n - 3 = \frac{3}{2}n-2 > n$, which is a contradiction.

The edge $(u,v)$ provides you with a cycle of length at most $2 (\lceil \log n \rceil - 1) + 1$. This cycle is is obtained as the union of $(u,v)$ with the unique path from $u$ to $v$ in $T$.