# 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?

-

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.

1. 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?)
2. 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.

-

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?

-
Why would it break the graph into two disconnected subgraphs? – Shawn Oct 17 '11 at 1:02
@Shawn It's interesting that you are asking me back the same question I left in my answer. :) Do you have any ideas? Suppose the edge is $e = (u,v)$. In the graph $G \setminus e$, can there be any path from $u$ to $v$? – Srivatsan Oct 17 '11 at 1:05