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

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.


Here is an argument that does not require any results about trees.

Suppose we start with an $n$-vertex graph that has no edges, and add $m$ edges to it, one at a time.

When does adding an edge create a cycle? A cycle using edge $vw$ in a graph $G$ consists of following a path from $w$ to $v$ not using the edge, and then taking the edge $vw$ to return to the start. So a new cycle is created whenever there was a path already between the endpoints of the new edge.

Therefore each new edge can do one of two things:

  1. Connect two vertices that were not connected before. This reduces the number of connected components by $1$, but creates no new cycles.
  2. Connect two vertices that were connected before. This creates at least one more cycle.

Since we have $n$ connected components initially, option 1 can happen at most $n-1$ times, so option 2 must happen at least $m-(n-1)$ times, creating at least $m-n+1$ cycles.

This minimum value can be achieved for relatively small $n$; for example, the friendship graph has $2n+1$ vertices, $3n$ edges, and exactly $n = 3n - (2n+1) + 1$ cycles. But eventually, we get more cycles than this; for example, with $\binom n2$ edges, our only option is the complete graph, which has many more than $\binom n2 - n + 1$ cycles: it has $\binom n3$ cycles of length $3$ alone.