Existence of cycle in a graph How does one show that any graph with $n$ vertices and at least $n$ edges must have at least one cycle?
 A: 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. 


*

*Show by induction on $n$ that a tree with $n$ vertices has $n-1$ edges. (HINT: What happens when you ‘pluck’ a leaf and its stem from a tree?)

*Show by induction on $k$ that a forest of $k$ trees with altogether $n$ vertices has $n-k$ edges.


Conclude that if a graph with $n$ vertices has more than $n-1$ edges, it can’t be a forest.
A: 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.
A: 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? 
