# Prove that every graph in which each vertex has degree at least 2 must contain a cycle. [duplicate]

This question already has an answer here:

Prove that every graph in which each vertex has degree at least 2 must contain a cycle. Graph has a finite number of vertices

I need some clarification, I understand that a vertex with degree 2 means having 2 neighbors. So this means that every vertex has two neighbors does this mean that the shape is a triangle with 3 vertices and 3 edges all connected or a square where each vertex is connected to two other vertices. Since they are connect it forms a cycle. However Im having trouble proving it, how will I go about proving this? Thanks in advance

## marked as duplicate by Ross Millikan, Macavity, JonMark Perry, draks ..., mlcMay 31 '17 at 5:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• You asked the same question a day ago here It seems you missed the point that a cycle can include all the vertices of a graph, so you can't just look at triangles and squares. You should update the other question rather than asking a new one. – Ross Millikan May 31 '17 at 3:06

## 1 Answer

Suppose the opposite. We have a graph which the degree of each node is 2, but there is no cycle. So, we know that if it is connected will be a tree and $v = e + 1$. Therefore, we can conclude for this graph, $e$ must be less than or equal $v - 1$. On ther hand, we know in this graph each node has degree 2, so $e = 2\times v / 2 = v$. This is contradicted by $e \leq v - 1$. Therefore, the first assumption is not true, and this graph has at least one cycle.