# Prove that there is a path of lenght k+1 in a graph with minimum degree k

I am faced with this question.

Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v_0, v_1, ..., v_k$ such that for $0 ≤ i < k$, $v_i$ is connected to $v_{i+1}$ in $G$.

I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$

• If $P$ is a maximal path, where do all the neighbors of the endpoint vertices need to go? – Louis May 1 '14 at 22:17

• It's also often instructive to try to find a graph that would make the theorem false: in this case, try to construct a graph of minimum degree $k$ that contains no $k$-path. – David Richerby May 1 '14 at 20:36