Graph of size n with girth >2k and minimum degree more than n^1/k
Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N_1 &gt; \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 &gt; \lceil n^{1/k} \rceil^k \geq n$, which is impossible.