Skip to main content
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Consider a graph $G$ where each vertex has degree at least two. Prove that this graph has a cycle.

One could prove this by arguing that we can start at a point, and just follow edges, until we meet an already visited vertex, but I think the following argument is slicker:

$G$ belongs to the complement of the set of forests, since every tree has a leaf, but $G$ does not. Forests are the only graphs that do not have cycles. Hence, $G$ has a cycle.

Post Made Community Wiki by Per Alexandersson