Minimum number of cycles of a graph with $n$ vertices, $m$ edges and $c$ components.

Question

Let $G$ be a graph with $n$ vertices, $m$ edges and $c$ components. Prove that $G$ contains at least $m-n+c$ cycles. My Professor just forwards this question during lecture time but I don't have enough information how to tackle the proof of this statement. Any help is appreciated.

Answer 1

Number of components in a forest $G$ is $|V(G)|$-$|E(G)|$, now, we have $c$ components and $n$ vertices, so the number of edges in the spanning trees of the graph is $n-c$. Now we have the remaining $m-(n-c)$ edges that are not part of the spanning tree. Whenever you add one of those edges to the spanning tree, you get a cycle. So you get at least $m-n+c$ cycles.