2

I'm not sure how to show that the graph G contains a cycle if the minimum degree delta ≥ 2 for the following question

Show that if G is a graph with minimum degree ≥ 2, then G contains a cycle.

ali
  • 21

2 Answers2

1

Hint:

Consider a path $v_1,v_2,\ldots,v_h$ of maximum length. (Here, by path, we mean explicitly not a cycle.) Now, you've used only one edge incident to $v_h$, but we know by assumption that there are at least two.

What could possibly keep this second edge incident to $v_h$, which we have not yet used in the path, from forming a path of longer length (which would be a contradiction to the assumption that our path is as long as possible)?

Nick Peterson
  • 32,430
0

I would do a proof by contradiction. Suppose that $G$ has $\delta(G) \geq 2$ but does not contain a cycle. Then $G$ is either a tree or a forest. If $G$ is a tree (the maximal case of acyclicity), then $G$ has $V - 1$ edges. From there, I would use a handshake lemma argument to get that there are at least $2V$ edges.

ml0105
  • 14,674
  • I need more help on this please. I can't figure it out. – ali Mar 17 '14 at 04:59
  • Please specify what you don't understand, and I'll be happy to expand! – ml0105 Mar 17 '14 at 05:02
  • How would I show that G is a minimum degree with delta ≥ 2 and show that is a cycle – ali Mar 17 '14 at 05:05
  • Use a handshake lemma argument like I described. The idea of proof by contradiction is to suppose that what you want to prove ($G$ has a cycle) is not true, then derive that it cannot be the case. You are given that $G$ has minimum degree of at least $2$, so you can assume that. You don't have to prove that. – ml0105 Mar 17 '14 at 05:09