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

  • $\begingroup$ 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? $\endgroup$
    – Casteels
    Jun 18, 2015 at 18:01
  • $\begingroup$ I counted 1 before removing $v_0$ so $k-1+1=k$ but yeah I can't justify what you said... $\endgroup$
    – shinzou
    Jun 18, 2015 at 18:03

2 Answers 2


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

  • $\begingroup$ I Thought about that at first but how can I be sure a different vertex was chosen at all times? $\endgroup$
    – shinzou
    Jun 18, 2015 at 18:13
  • $\begingroup$ @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. $\endgroup$ Jun 18, 2015 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.

  • $\begingroup$ 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$ ? $\endgroup$
    – MT_
    Jan 31, 2016 at 16:41
  • $\begingroup$ 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. $\endgroup$
    – bilaterus
    Jan 31, 2016 at 16:44
  • $\begingroup$ OH. A path of length $m$ has $m+1$ vertices! Thanks for making me stare at it @Soke . $\endgroup$
    – bilaterus
    Jan 31, 2016 at 16:50
  • $\begingroup$ @bilaterus so the answer holds true? $\endgroup$
    – Carlo
    Jan 31, 2016 at 17:55
  • $\begingroup$ @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. $\endgroup$
    – bilaterus
    Jan 31, 2016 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .