Problem
COM-B1-M09-P014 At Least as Many Edges as Vertices
#14
★★★☆☆ Level 3 of 5
Prove that if a graph on \(n\) vertices has at least \(n\) edges, then it contains a cycle.
A graph without cycles is a forest.
If the graph has no cycles, each connected component is a tree. If the component sizes are \(n_1,\ldots,n_k\), then the number of edges is \((n_1-1)+\cdots+(n_k-1)=n-k\le n-1\). Thus an acyclic graph has at most \(n-1\) edges. If there are at least \(n\) edges, a cycle must exist.
First serious argument using forests.