Graph of size n with girth >2k and minimum degree more than n^1/k

Question

I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$.
The proof is made by contradiction where repeatedly any node from $G$ of degree at most $\lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $G'$ of $G$ of minimum degree more than $\lceil n^\frac{1}{k}\rceil$.
The conclusion is that $G'$ must have girth at most $2k$ and therefore also $G$, which is a contradiction.

I don't understand the conclusion: Why must $G'$ have girth at most $2k$? Why is it not possible that $G$ has girth more than $2k$ and minimum degree more than $\lceil n^\frac{1}{k}\rceil$?

I don't really see an answer to this question, so I would be very grateful if someone can help me.

Answer 1

Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N_1 > \lceil n^{1/k} \rceil$ neighbors. Each neighbor of $v$ has more than $\lceil n^{1/k} \rceil$ neighbors, and at least $\lceil n^{1/k} \rceil$ of them are different from $v$. The neighbors of different neighbors are all different, since otherwise $G'$ would have a 4-cycle. Denoting by $N_2$ the number of nodes at distance 2 from $v$, we have $N_2 \geq \lceil n^{1/k} \rceil N_1$. Continuing this way, we have $N_\ell \geq \lceil n^{1/k} \rceil N_{\ell-1}$ for all $\ell \leq k$ (here you use the lower bound on the girth; details left to you). In total, we get $N_k > \lceil n^{1/k} \rceil^k \geq n$, which is impossible.