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.