Prove that every undirected finite graph with vertex degree of at least 2 has a cycle

Start anywhere, and follow the edges. You'll always be able to continue, since each vertex has degree at least 2, so there will be an unused edge to exit on. If you ever return to a vertex where you've been, you've got a cycle. Otherwise, if the graph is finite, eventually you'll run out of unused vertices and you'll have to revisit some vertex.


Of all simple paths in $G$, find one with the most number of vertices, call it $P$. Let $v$ be one of the endpoints of the path, which must have at least one other neighbour. Since $P$ is maximal this neighbour already belongs to $P$, forming a cycle.

[This is somewhat constructive in that it gives partial information about where a cycle lies. Essentially it is the standard proof that every (non-tiny) tree has at least two leaves, alluded to in Brian's answer.]


If you’ve already learned about trees, you know that if $G$ is connected and does not have a cycle, then it’s a tree. Even if it’s not connected, its connected components must be trees (i.e., $G$ itself is a forest). And every tree has at least one leaf ...

Tags:

Graph Theory