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.

The question I have is:

Prove that the minimum number of cycles is $m-n+1$ in a connected graph. Where one cycle is a path that starts that begins and ends at the same vertex. Where $m$ is edges and $n$ is the vertices.

I have no idea where to start. A few hints would be appreciated. Please do not provide me with the answer.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Hint: Consider a spanning tree of the graph. What happens when you add edges?

Let me first define what a tree is formally: A tree is a connected graph which contains no cycles. A leaf is a vertex of the tree which has degree $1$.

There are quite a few definitions which are equivalent, I shall choose one of the simplest and the one most suited for our application here.

Here are a few things which you will need to prove. These are not very long, if you have a proof which is very complicated then you've probably gone wrong somewhere. I've added hints in spoiler tags. Perhaps one thing I should mention. Do not let the abstract terms and definitions bog you down; a tree is exactly what you think it is (no, not the things outside). Your intuition will serve you well, you only need to take a bit of care to convert your intuition properly into a proof.

1. Every tree has at least two leaves.

Hint: Consider "walking" through the tree. Can we continue this process indefinitely? Where must we end up?

2. A tree on $n$ vertices has precisely $n-1$ edges.

Hint: Use the above fact and induction.

3. Adding any edge to a tree will create a cycle.

Hint: If you add an edge $(u,\ v)$ then can you find two different paths now from $u$ to $v$?

Now a spanning tree is a connected, cycle-less subgraph of a connected graph which contains every vertex.

4. Every connected graph has a spanning tree.

Hint: Induct on the number of edges.

These should be enough to provide a very rigorous proof of your fact.

share|improve this answer
    
Can you please provide an example, we haven't learned "spanning tree" yet. –  Jeel Shah Oct 30 '12 at 22:21
    
Hmm. The concept is rather simple if you're willing to accept the fact that a spanning tree actually exists (which does require proof). Basically it's a connected sub-graph of the original graph which is cycle-less and contains every vertex. Have you learned about the numerous equivalent properties which characterize a tree? –  EuYu Oct 30 '12 at 22:25
    
If you want, I can provide a proof that every connected graph has a spanning tree. But I think it's a good exercise to try yourself. –  EuYu Oct 30 '12 at 22:28
    
We haven't learned the equivalent properties yet and an example of a spanning tree would be great. –  Jeel Shah Oct 30 '12 at 22:32
    
Your teacher told you to prove this without introducing trees at all? What do you have to work with? As for examples, you can find quite a few just by googling spanning tree. Take a look here for example. –  EuYu Oct 30 '12 at 22:33

If you learned what a tree is, you can do induction by $m$.

If $m=n-1$, then your graph is connected and satisfies the tree formula, so how many cycles are there.

The inductive step is easy: If you have a graph on $m+1$ edges, then $m+1>n+1$ thus your graph is not a tree, and hence must have a cycle. remove one edge from the cycle, use induction and add it back...

share|improve this answer

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.