Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$

Prove there's a simple path of length $k$ in a simple graph $G$ where all the vertices have degree of at least $k$.

Relevant definitions:

$G$ is a simple graph that consists of a vertex set $V(G) = \{v_1, v_2, ..., v_n\}$ and an edge set $E(G) = \{e_1, e_2, ..., e_m\}$ where each edge is an ordered pair of vertices. The edge $\{u,v\}$ is denoted $uv$. A walk of length $k$ is a sequence $v_0,e_1,v_1,e_2,...,e_k,v_k$ of vertices and edges such that $e_i=v_{i-1}v_i$ for all $i$. A path is a walk with no repeated vertex.

My attempt:

Induction, for $k=1$ it's obvious.

Suppose for $k-1$ and we'll prove for $k$.

Let $G$ be a simple graph such that $\forall v \in V : d(v)\ge k$.

We can assume that there are at least $k+1$ vertices since there are $k$ neighbours to every vertex.

Let $v_0$ be some vertex, it has $k$ neighbours, we'll move to one of its neighbours say $v_1$ and remove $v_0$. So now there are $k$ vertices with a degree of at least $k-1$ and from the induction hypothesis we'll have a path of length $k$.

Is using only $k$ vertices from $n$ right? Does it keep the generality when using only all the neighbours of $v_0$?

Solution 1:

The problem with that approach is that the path of length $k-1$ in $G-v_0$ may not have a vertex adjacent to $v_0$ at either end, so you may not be able to extend it to a path of length $k$ in $G$.

You don’t actually need induction on $k$. Start at any vertex $v_0$. It has degree $k$, so it’s adjacent to some vertex $v_1$. Assuming that $k>1$, $v_1$ is adjacent to at least one vertex $v_2$ other than $v_0$. If $k>2$, then $v_2$ is adjacent to at least one vertex $v_3$ different from $v_0$ and $v_1$. And so on. In general you can continue this argument until you’ve chosen $v_k$ adjacent to $v_{k-1}$ and different from $v_0,\ldots,v_{k-2}$, at which point you have a path of length $k$.

Solution 2:

Suppose the length of the longest path is $m<k$ and take a look at one of the paths (say it's made up of vertices $v_1, v_2,\dots,v_{m+1}$).

Consider $v_{m+1}$. It cannot be connected to vertices outside of the path, because then we could form a longer path and contradict maximality. Hence it can only be connected to some of the other $v_i$ (given it is a simple graph). But there are only $m<k$ of those, so this contradicts the minimum degree condition of the graph.