Let $G= (V, E)$ be a connected graph with minimal degree $\delta(G) \geq k$ and $|V| > 2k$. Show that there exists a Path containing $k+1$ vertices.
I thought about considering the longest path in $G$, i.e. $P = (v_0, v_1,\ldots, v_{s}).$ This path must contain all of $v_0$'s neighbours since if it didn't contain one of them, we could simply extend the path by this vertex. Because $\text{deg}(v_0)\geq k$ the path must be of length $k+1$. Does this already prove the statement?
Best Answer
Yes, that's correct. In fact (provided $k>1$), it proves the graph contains not only a path on $k+1$ vertices, but a cycle on $k+1$ vertices: $v_0$ has $k$ neighbours, all on the path, so the largest $r$ such that $v_r$ is a neighbour of $v_0$ is at least $k$. Then $v_0v_1\cdots v_r$ is a cycle and has $r+1\geq k+1$ vertices.
Note that in your final paragraph you say the path "must be of length $k+1$". This is not correct, since a path of length $k+1$ has $k+1$ edges, and you only necessarily have $k+1$ vertices (but $k+1$ vertices is what the problem asked for, and is the best you can do).