1

There are two questions that essentially asked the same thing. One is categorized as a repetition but I just don't feel the other one's answers are valid. Let $G$ be a graph of minimum degree $k>1$. Show that $G$ has a cycle of length at least $k+1$ For the first answer that got 9 upvotes, it doesn't explain why every neighbour of a vertex is on the path P. Path doesn't allow repeating vertices so I don't see explicitly how one can travel from the node to all its neighbors and back without going through the node itself. If it travels outside the picture, say goes on to another node and tries to come back, I don't see how it can do that explicitly either. Any help appreciated.

Community
  • 1
Mikety2520
  • 41
  • If you consider the case when $G$ is a cycle, then you can visit both neighbors of $v_0$ by going all the way along the cycle $G$. Yes, you are allowed to visit other nodes along the way. – angryavian May 26 '16 at 00:37

1 Answers1

2

We prove by induction on $d$. If $d = 1$ there is an edge, and this is the needed path. Suppose $d ≥ 2$, the result is true for $d < D$, and minimum degree of your graph is $d$. By the induction hypothesis $G$ has a path $P$ of length at least $d − 1$. If the length of $P$ is at least $D$, then we’re done. So suppose the length is $D − 1$ and the sequence of vertices is $v_1, . . . , v_D$. The vertex $v_1$ has at least $D$ adjacent vertices, so there is a vertex $w$ which is adjacent to $v_1$, but is not on the path $P$. Thus $w, v_1, . . . , v_D$ is a path in $G$ with $D$ edges.

Now we prove that if $D ≥ 2$, the $G$ has a cycle of length at least $D + 1$. Let $P = v_0, v_1, . . . , v_m$ be a path of maximum length in $G$. The argument of previous part shows that $m ≥ D$, and that every vertex $w_d$ adjacent to $v_0$ is on the path $P$. Suppose, starting at $v_0$, the vertices $w_d$ appear in the order $w_1, . . . , w_L$. Then extend the path $v_0, . . . , w_L$ to a cycle by adding the edge $w_Lv_0$. The resulting cycle has at least $D + 1$ vertices, and thus has length at least $D + 1$.

Ken
  • 780
  • Thanks a lot for answering and the explanation. I still have a question: why do you know every vertex on wd adjacent to v0 is on the path P? I mean, you don't necessarily know all d-1 edges that are adjacent to v0 forms a path by themselves right? – Mikety2520 May 26 '16 at 02:50
  • 1
    Because we assumed that path $P = v_0, \cdots, v_m$ has maximum length in $G.$ So if there exist a vertex $w_d$ which is not adjacent to $v_0$ and also it is not on the path $P$, then you can make a longer path only by adding that vertex to $P$ and this is contradiction with the assumption that path $P$ has maximum length in your graph. – Ken May 26 '16 at 16:24