How does one show that any graph with $n$ vertices and at least $n$ edges must have at least one cycle?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Here's a direct proof strategy: You can assume without loss of generality that no vertex has less than two adjacent edges. (Why?). Start at a random vertex and wander aimlessly through the graph, being careful never to double back along the edge you just came from. You win if you reach any vertex you've been to before. You lose iff you reach a dead end or continue forever without winning. Prove that you always win.
Here’s a slightly different approach. A tree is a connected graph without cycles. A forest is a graph without cycles; its connected components are trees.
Conclude that if a graph with $n$ vertices has more than $n-1$ edges, it can’t be a forest.
HINT Here's a proof strategy. Depending on the level of the answer expected, you might have to fill in the missing details.
Suppose $G$ is an acyclic graph with $n$ vertices and $m$ edges. Our goal is to prove that $m \leq n-1$. Now deleting an edge in $G$ breaks the graph into two disconnected subgraphs (why?) $C_1$ and $C_2$ with $n_1$ and $n_2$ vertices respectively, where $n_1, n_2 < n$.
Can you complete the proof via (strong) induction?