1

Hello can you help me to prove this. The hint for the problem is: Think of what it means for a graph to have no cycles.

So I believe this will be a contrapositive proof, but still could not do it.

AS8x
  • 11
  • Note that you need the number of vertices to be finite. For an infinite counter example, start with 1 root which has 3 children, and each of the children has 2 children. Continue to infinity. – Calvin Lin Oct 10 '13 at 21:21
  • Yes, the professor said the it is a finite graph. But I was still not able to prove this mathematically. can you please give me some hints? – AS8x Oct 11 '13 at 00:18
  • My graph theory is rusty, but I would also use a contrapositive proof. If the graph has no cycles, and it is finite, then I think all its components have to be trees, and a tree has a vertex with degree 1. See Daniel's answer. – Stefan Smith Oct 11 '13 at 02:33

4 Answers4

1

Hint: If a graph with $n$ vertices does not have cycles, then we have a tree and the sum of degrees is at most $2n-2$.

Hence, if the degrees of each vertex is at least 3, the sum will be at least ........

Calvin Lin
  • 68,864
1

Proposition. A finite undirected graph whose vertices all have degree $\geq2$ contains a cycle.

Proof. Start at vertex $v_1$ along any edge and proceed recursively as follows: When you reach a vertex which you have not seen before proceed along any edge which you have not used arriving at that vertex. The first time you arrive at a vertex which you have seen before, stop: You have completed a cycle. Since there are only finitely many vertices the procedure has to come to a halt.

Christian Blatter
  • 226,825
0

A graph with no cycles is called a "tree." (Well, technically, a "forest," but each connected piece is called a tree.) Here's a picture of a tree:

enter image description here

Do you see some vertices there which have degree not equal to three? Do you see why certain types of them would be unavoidable in a tree?

Daniel McLaury
  • 24,656
  • Hi Daniel, thank you for the graph. Yes, I totally know that it has to have cycle in order for all its vertices to have degree of 3. I just do not know how to prove it mathematically. This is for discrete math. – AS8x Oct 10 '13 at 23:59
0

Hint: The graph must be finite for there to be a cycle. For a finite graph where every vertex has degree $\geq 2$, start at an arbitrary vertex. Take all neighbors of the vertex, then take all neighbors of vertices such that the neighbors were not visited in the previous iteration, etc. Show that when you continue to iterate, you must arrive at a vertex you previously visited, or two vertices must be neighbors of the same vertex in the next iteration. Then this will give you a cycle.

user2566092
  • 26,142
  • It is not true that a graph must be finite for there to be a cycle. There could be infinitely many vertices, but a cycle involves finitely many points... I can also easily create a infinite graph, each of which have degree 3, but there are no cycles. – Calvin Lin Oct 10 '13 at 21:20
  • Hi, so how can I technically show that when I continue to iterate, I must arrive at a vertex that is already visited? – AS8x Oct 11 '13 at 00:54