# 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$?

• Won't the induction hypothesis only guarantee a path of length $k-1$? And how do you now the path of length $k-1$ has $v_1$ as an endpoint? – Casteels Jun 18 '15 at 18:01
• I counted 1 before removing $v_0$ so $k-1+1=k$ but yeah I can't justify what you said... – shinzou Jun 18 '15 at 18:03

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$.

• I Thought about that at first but how can I be sure a different vertex was chosen at all times? – shinzou Jun 18 '15 at 18:13
• @kuhaku: That’s built into the construction that I outlined: you simply choose a different one each time. That you can do this is guaranteed by the degree constraint. It’s only after you’ve chosen $k+1$ vertices that you might no longer be able to extend the path to a new vertex. – Brian M. Scott Jun 18 '15 at 18:14

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.

• What if it's connected to a vertex outside of the path which never leads back to $v_1$ ? IS that not possible? Also, doesn't this argument work also if $m = k$ ? – MCT Jan 31 '16 at 16:41
• Since we're only looking for a path, if $v_m$ is connected to $v_{m+1}$ outside of the original $v_i$, then $v_1 \dots v_{m+1}$ is a longer path, contradicting maximality. Also, the argument should work if $m=k$, which I think is fine because I'm pretty sure there is supposed to be a maximal path of length $k+1$... but it has been a long time. – bilaterus Jan 31 '16 at 16:44
• OH. A path of length $m$ has $m+1$ vertices! Thanks for making me stare at it @Soke . – bilaterus Jan 31 '16 at 16:50
• @bilaterus so the answer holds true? – Carlo Jan 31 '16 at 17:55
• @user3071799 yes, I fixed it. the argument is correct (and quite a useful one) though I'd gotten a detail wrong. It's all fixed now. – bilaterus Jan 31 '16 at 18:55