Consider any undirected, unweighted graph $G = (V, E)$ with the property that every vertex in $V$ has degree at least $3n^{1/4}$ in $G$ where $n=|V|$. Prove that $G$ contains a cycle with $8$ edges or less.
What I tried: I wanted to do BFS from a random vertex in the graph to find the cycle, but I feel like there must be a simpler way to prove this.
Best Answer
I've came up with a pretty simple proof, though it was inspired by BFS. However, I think one can read the proof without knowing BFS.
Let $G = (V, E)$. We firstly choose $v_0 \in V$ arbitrarily.
Let $S_i = \{ v \in V \mid \mathrm{distance}(v_0, v) = i \}$. For $G$ not to contain cycles with length $\leq 8$, we must satisfy the following:
Proof for 1. Suppose there is such an edge $xy$. Let the shortest path between $v_0$ and $x$ be $v_0 = s_0, s_1, \dots s_{i-1}, s_i = x$, and let the shortest path between $v_0$ and $y$ be $v_0 = t_0, t_1, \dots, t_{i-1}, t_i = y$. For maximum $j$ that $s_j = t_j$, $(s_j, \dots, s_{i-1}, x, y, t_{i-1}, \dots, t_j)$ is a simple cycle, because endpoints $s_j$ and $t_j$ are the same, and the other vertices are different, and the length is any of $3, 5, 7$.
Proof for 2. Suppose there are such two edges $xy$ and $xy'$. Let the shortest path between $v_0$ and $y$ be $v_0 = s_0, s_1, \dots s_{i-1}, s_i = y$, and let the shortest path between $v_0$ and $y'$ be $v_0 = t_0, t_1, \dots, t_{i-1}, t_i = y'$. For maximum $j$ that $s_j = t_j$, $(s_j, \dots, s_{i-1}, y, x, y', t_{i-1}, \dots, t_j)$ is a simple cycle, because endpoints $s_j$ and $t_j$ are the same, and the other vertices are different, and the length is any of $4, 6, 8$.
I wrote these two proofs formally so it's a bit long; but the idea for both proof is simple, that we can create cycle with length $\leq 8$ by "merging" two shortest paths.
Let the minimum degree of $G$ be $\delta$. Obviously, $|S_0| = 1$ and $|S_1| \geq \delta$.
For $i = 1, 2, 3$ and $y \in S_i$, all vertices adjacent to $y$ except one of them (refer to Condition 2) are in $S_{i+1}$. Thus, letting $m$ is the number of edges connecting $S_i$ and $S_{i+1}$, it holds $m \geq |S_i| \cdot (\delta - 1)$. However, because of Condition 2, for all $x \in S_{i+1}$, there should be only one such $y$, so $m = |S_{i+1}|$ must hold. Therefore, we derive $|S_{i+1}| \geq |S_i| \cdot (\delta - 1)$.
Due to this inequality, we derive $|S_2| \geq \delta (\delta - 1)$, $|S_3| \geq \delta (\delta - 1)^2$, and $|S_4| \geq \delta (\delta - 1)^3$. Therefore:
$$n \geq |S_4| = \delta (\delta - 1)^3 \geq (\delta - 1)^4 \Leftrightarrow \delta \leq n^{1/4} + 1$$
And of course, since $n^{1/4} + 1 \leq 3 n^{1/4}$ for all $n$, this bound is enough for the claim.