We can assume that each vertex is of degree where .
The key concept is that there must be at least vertices in the graph.
Start at any vertex. There are vertices adjacent to that vertex.
Choose a second vertex adjacent to the first. Now there are vertices, other than the first, adjacent to the second vertex.
Do you see how finish?