7
$\begingroup$

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

$\endgroup$
  • $\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 '15 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 '15 at 18:03
6
$\begingroup$

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

$\endgroup$
  • $\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 '15 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$ – Brian M. Scott Jun 18 '15 at 18:14
4
$\begingroup$

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.

$\endgroup$
  • $\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$ – MCT Jan 31 '16 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 '16 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 '16 at 16:50
  • $\begingroup$ @bilaterus so the answer holds true? $\endgroup$ – Carlo Jan 31 '16 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 '16 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.