Assume that the graph is asimple graph. Apathis an alternating sequence of vertices and edges in which on vertex is repeated. (Now in Graph Theory definitions will vary, but this argument should work.)

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?