I went into this problem when I was trying to prove that for all graph $G$ with $n$ vertices and no less than $n+k$ edges, it has at least $k+1$ cycles. ---(1)
In this question, there is no assumption of connected. What I was thinking about is do an induction on $k$, but $k$ does not goes to natural numbers, but is bounded by $n!$.
At the last step of my induction step, I was trying to prove that if number of vertices $|V| = n$, and $|E| = n+k$, with exactly $k+1$ cycles, then the graph $G$ is connected. ---(2)
I couldn't think of a proof for the bold statement, and not quite sure if it is correct. Any suggestion of approaching to (1) and (2) would help. Thanks a lot.
We show that $G$ must be connected as follows: Let $S$ be a minimum-cardinality set of edges so that $G \setminus S$ has no cycles. Then note the following: As $G$ has exactly $k$ cycles, $|S|$ is no larger than $k$. Thus $G \setminus S$ is a graph on $n$ vertices with no cycles and at least $n-1$ edges.
We claim that $G$ has exactly $n-1$ edges, as every graph $G$ on $n$ vertices with $n$ or more edges has a cycle.
However, all graphs $G$ on $n$ vertices, with $n-1$ edges, and no cycles are trees, and thus connected.