Problem
COM-B2-M07-P009 Exactly One Cycle
#9
★★★☆☆ Level 3 of 5
A connected graph on \(n\) vertices has \(n\) edges. Prove that it contains exactly one cycle.
Compare the graph with its spanning tree.
Take a spanning tree of the graph. It has \(n-1\) edges, so the original graph has exactly one edge outside this spanning tree. Adding one edge to a tree creates exactly one cycle.
Every cycle of the original graph must use this single extra edge, because the tree itself has no cycles. Therefore there is exactly one cycle.
This is the first cyclomatic-counting problem without terminology.