# Prove that the minimum number of cycles is $m-n+1$

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.

-
The statement is not phrased in the best way. You want to prove that the number of cycles is at least $m-n+1$, and this is what's given in the answers. The function for the minimal number of cycles grows faster if $m$ is big. –  domotorp Apr 16 at 19:48

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.

-
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...

-