A graph without cycles Show that: if a graph G has $n$ vertices and no cycles of length shorter than $2k + 1$, then the number of edges is at most $n(n^{\frac{1}{k}} +1)$
My idea is use BFS on a vertice of minimum degree. But its not clear to me how to use the hypothesis. Any help would be greatly appreciated! 
 A: The proof is simple, it's by decending induction on $k$.
If $k=n$. Then $E=n\leq n(n^{\frac{1}{n}}+1)$.
Suppose it's true for $k$ and let's prove it for $k-1$. Since $G$ has no cycles of length $2(k-1)+1$ then the smallest cyle is of length $l> 2(k-1)+1 =2k-1$. 
If $l\geq 2k+1$, then by induction $|E|\leq   n(n^{\frac{1}{k}}+1)$. Then  $|E|\leq   n(n^{\frac{1}{k}}+1)<n(n^{\frac{1}{k-1}}+1)$.
If $l=2k$, let $c$ be the number of cycles of length $2k$. Note that $c\leq \frac{|E|}{2k}$ (Since the length of each  cycle of the $c$-cycles is  $2k$, and every two cycles have at most one common vertex,  then $c\leq \frac{|E|}{2k}$). Let $G'$ be the graph obtained from $G$  by doing the following: $\forall$ cycle C of length $2k$ replace any edge of $C$ by two edges with a vertex outside the cycle. Then $G'$ has no cycle of length shorter than 2k+1. Thus by induction $|E(G')|\leq n(n^{\frac{1}{k}}+1) $. Note that $|E(G')| = |E|+c$. Thus   $|E(G')|=|E|+c =|E|(1+\frac{1}{2k})\leq n(n^{\frac{1}{k}}+1)$. Thus $$|E|\leq \frac{2k}{2k+1} n(n^{\frac{1}{k}}+1)<n(n^{\frac{1}{k-1}}+1)$$
