Let $G=(V,E)$ be a nonempty graph and let $d(v)\geq k$ for all $v\in V$. Prove that there exists a path in $G$ of length $k$.
Alright so my first intuition is
$$\sum_{i=1}^{n} d(v_i) \geq nk \quad(n=|E|)$$
So a path contains each vertex once and has no cycle. Seeing as each vertex has a degree $\geq k$, in the worst situation (because this limits the length of our path) we have:
$$\sum_{i=1}^{n} d(v_i) = nk$$
We also have $\sum_{v\in V} d(v_i) = 2|E|$, so
$$
2|E| = nk.
$$
This seems logical but I cant translate this into the length of a path. Any tips?
edit
maybe we can say because we have $\frac{nk}{2}$ edges, and $n$ vertices, we could maybe use induction?
Best Answer
Hint. Pick a vertex $v_1$. It is connected to $k$ vertices. Pick one of them $v_2$, this is connected to $k$ vertices, and $k-1$ of them are not in the path (only $v_1$ can be).
$v_2$ is connected to at least $k-2>0$ vertices not in the path. Pick one of them, $v_3$ repeat....
Induction by $k$ is probably the simplest way to write the solution....