Prove that if all the vertices of a graph have degree 3, then the graph must have a cycle 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. 
 A: 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 ........
A: 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:

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?
A: 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.
A: 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.
