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.
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:
- Connect two vertices that were not connected before. This reduces the number of connected components by $1$, but creates no new cycles.
- 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.