0

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

a_student
  • 51
  • 1
    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 03:06

1 Answers1

0

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.

OmG
  • 3,138