Let G be a graph on n vertices. Prove that if $|E|\geq 2kn$. then G contains a path of length k.
($|E|$ denote number of edges)
My attempt: I am proving this using induction on variable $k$.
$n\geq 1$
$k=1$, $|E|\geq 2n\ge 2 \implies $ there exists atleast two edges. so, there is a path of single edge.
For, $k=m$ assume this result. We have to prove for $k=m+1$
Graph with $n\geq 1$ vertices and $|E|\ge 2(m+1)n=2mn+2n\geq 2mn.$ By our assumption. There is a path of length $k$. Also, $|E|$ has $2n$ more edges than case where $k=m$.
suppose where the case one of the edge from $2n$ edges. one edge adjecent to the end of path. We are done. What of those $2n$ adges are not adjecent othe endpoints of the path?
Best Answer
By the answer to this question if the degree of each vertex of your graph $\Gamma$ is at least $k$, there is a path of length $k$ in $\Gamma$. So suppose that the degree of some vertex $v$ is $<k$.
Induction by $n$ (not $k$). Remove the vertex $v$ with all its edges. The number of vertices in the new graph $\Gamma'$ becomes $n-1$, the number of edges is at least $|E|-k\ge 2nk-k=2k(n-1/2)>2k(n-1)$. So $\Gamma'$ (hence $\Gamma$) has a path of length $k$ by induction on $n$. The base of induction: $n=1$.