4
$\begingroup$

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.

  • 0
    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.2015-04-16

3 Answers 3

4

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.

  • 0
    Yes, that would be great. Thanks2012-10-30
2

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.

  • 0
    (Yes, this is a very old question, but I figured that since it came up recently, it was worth adding this very simple argument as an answer.)2018-06-18
0

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

  • 0
    How do we know that adding one edge only adds one cycle? I agree this shows that $m-n+1$ is a lower bound, but do we know it is attained?2018-06-18