# Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that $H$ contains at least $m-n+1$ cycles.

Can someone please verify the proof I just wrote, or offer suggestions for improvement? Also, how do I prove the base case?

Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that $H$ contains at least $m-n+1$ cycles.

We can proceed by induction on $m$, the number of edges. Clearly, the statement is true for all $m < n$. Suppose the statement is true for some $m \geq n$. Consider a graph $G$ with $n$ vertices and $m+1$ edges. By the inductive hypothesis, $G-e$ has at least $m-n+1$ cycles. If it has more than $m-n+1$ cycles, we are done, as $G$ will have at least $m-n+2$ cycles. Suppose, instead that $G-e$ has exactly $m-n+1$ cycles. Pick a cycle $C$ of $G-e$ and pick an edge $e'$ of that cycle.

Again, by the inductive hypothesis, $G-e'$ has at least $m-n+1$ cycles. If it has more than $m-n+1$ cycles, we are done. If, instead, it has exactly $m-n+1$ cycles, then there must be a cycle $C'$ not in $G-e$ (otherwise $G-e'$ would have only $m-n$ cycles). But then, $G$ has at least $m-n+2$ cycles, of which $m-n+1$ are in $G-e$, and one of which is in $G-e'$ and not $G-e$.

This completes the proof.

## 1 Answer

The proof is incorrect, though the idea is correct. The base case is missing ($m=n$), since your inductive step assume that the previous case have a cycle, so $m<n$ does not work as a base case.

However, may I suggest a simplification?

Once you got a graph with $m+1$ edge, simply use the fact that there is at least 1 cycle (since $m+1\geq n$ and maximum edge in cycleless graph is $n-1$, a fact you probably use in your base case anyway), to pick out edge $e$ in a cycle $C$. Then $G-e$ have $m-n+1$ cycle, and now add in the cycle $C$ (which is not in $G-e$ since it contains $e$) to complete the induction.