1

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

I know that a vertex is a node and the only way for it to have a cycle is that when there are three vertices and three edges and that the shape is of a triangle. However I dont know how to prove it.

Thanks in advance

a_student
  • 51

1 Answers1

3

I assume your graph has a finite number of vertices, as otherwise the statement is not true. Just start somewhere and follow the path. If you ever have an option to go back to a vertex you have visited, you have found a cycle. You can never get stuck as each vertex you come to has an exit. Eventually you will run out of vertices.

Ross Millikan
  • 374,822