Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How does one show that any graph with $n$ vertices and at least $n$ edges must have at least one cycle?

share|improve this question

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer

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?

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.