If ${\lvert{E(G)}\rvert}>{\lvert{V(G)}\rvert}+3$, graph $G$ has at least two disjoint cycles. Assume that $G$ is a graph which ${\lvert{E(G)}\rvert}>{\lvert{V(G)}\rvert}+3$. Prove $G$ has two disjoint cycles.

Answer:
I tried to prove it when $G$ is connected. consider the smallest cycle of length $k$. It exists because ${\lvert{E(G)}\rvert}>{\lvert{V(G)}\rvert}-1$.
Now, I divided vertices into $2$ groups. Group $A$ consists of $k$ vertices in the smallest cycle and group $B$ consists of the other $n-k$ vertices.
Now, between  $n-k$ vertices are exactly $n-k-1$ edges. Because, If it is more then we have another cycle (the proof is done) and if it is less then $G$ is disconnected (contradiction). So there are at least $5$ edges between group $A$ and $B$.
Now, what should I do? should I write every possibility to prove it? Are there any easy ways to continue the proof?
What about if $G$ is disconnected? I think we should do it in each component. Am I right?
Thank you so much for your answers.
 A: Suppose the result is false; take a minimal counterexample $G$ with $n$ vertices and exactly $n+4$ edges (if there were more edges, we could delete some).
Then $G$ cannot contain a $3$-cycle or $4$-cycle. Otherwise, removing the edges of such a cycle, we have a graph with $n$ vertices and at least $n$ edges, which must still contain another cycle.
Also, $G$ has minimum degree $3$. If $G$ had a vertex $v$ of degree $1$, we could delete it and the edge out of it, getting a smaller counterexample (since the leaf was not part of any cycle). If $G$ had a vertex $v$ of degree $2$, with neighbors $w_1, w_2$, we could replace $v$ and its two edges with the single edge $w_1w_2$. This also gives a smaller counterexample, since any cycle containing $v$ would have had to use both edges, and now it can use the edge $w_1w_2$ instead. Also, because $G$ had no $3$-cycle, this still gives a simple graph.
Since $G$ has minimum degree $3$ and $n$ vertices, it must have at least $\frac 32n$ edges, but we know it has exactly $n+4$. Therefore $n+4 \ge \frac32n$, or $n \le 8$.
However, if we take a vertex $v$, we know it must have at least $3$ neighbors $w_1, w_2, w_3$. These have no edges between them (because $G$ has no $3$-cycles) and each has $2$ more neighbors (by minimum degree $3$) which are all distinct (because $G$ has no $4$-cycles), giving us at least $10$ vertices already. This is a contradiction, so the result must be true.
A: The case by case analysis can be made to work. The key is to organize your cases carefully. It's not clear a priori how this is done, but it turns out that a good way is to look at how each connected component obtained by the removal of the cycle intersects the cycle.
Theorem: Any graph satisfying $|E| \ge |V|+4$ has two (edge) disjoint cycles.
Proof: It suffices to prove that every graph satisfying $|E| = |V|+4$ has two (edge) disjoint cycles. This clearly implies the original statement since we can always delete edges until we have $|E|=|V|+4$, and any cycles of the remaining subgraph will be cycles of the original graph as well.
Now suppose for the sake of contradiction that the statement is false. Let $G$ be a counter-example. Let $C$ be any cycle in $G$. Removing the edges of $C$ must leave a cycle-free graph since any remaining cycles would be edge-disjoint with $C$. Therefore $G\backslash C$ is a forest. Let $\{T_1,\cdots,T_c\}$ denote the components of the forest. The number of components $c$ of the forest satisfy $|E|-|C| = |V|-c$. This implies that $|C|=4+c$.
Now, consider the vertices common to each component $T_i$ and $C$, which we will denote as $V_i$. On the one-hand, we must have
$$\sum_{i=1}^c|V_i| = |C|,$$
since each vertex of $C$ belongs in a unique component tree. On the other-hand, since $|C|=4+c$, it follows at least some of the $|V_i|$ must be larger than $1$, i.e., some of the trees must form chords of $C$.
Now we split into a few cases. In each case, we will construct two disjoint cycles, contrary to assumptions. For vertices $u,v\in V_i$, I will write $u\rightarrow v$ to indicate a path in $C$ from $u$ to $v$ and $u\Rightarrow v$ a path from $u$ to $v$ in $T_i$.
Note that the reasoning below is formal, but the various cases have easy and intuitive geometric interpretations. I suggest drawing out each of the cases if you find it difficult to follow.

*

*Suppose that there exists some $i$ such that $|V_i|\ge 4$. Let $v_1,v_2,v_3,v_4 \in V_i$ be four arbitrary intersection points, taken in sequence along $C$, i.e., $C = v_1\rightarrow v_2 \rightarrow v_3 \rightarrow v_4 \rightarrow v_1$. Then there exists a path $v_1\Rightarrow v_2$ and a path $v_3\Rightarrow v_4$. If these two paths are edge disjoint in $T_i$, then we are done, since our disjoint cycles are $v_1\rightarrow v_2 \Rightarrow v_1$ and $v_3\rightarrow v_4 \Rightarrow v_3$. Otherwise, there exists vertices $u_0,u_1$ where the paths $v_2\Rightarrow v_1$ and $v_3\Rightarrow v_4$ first and last meet. Then $v_1\Rightarrow u_1 \Rightarrow v_4 \rightarrow v_1$ and $v_2 \Rightarrow u_0 \Rightarrow v_3 \rightarrow v_1$ are disjoint cycles.


*Suppose that there exists some $i$ such that $|V_i|=3$. Let $v_1,v_2,v_3 \in C$ be the points of intersection. There must exist some other component $T_j$ such that $|V_j| \ge 2$. Let $u_1,u_2 \in V_i$. Then $C\backslash\{u_1,u_2\}$ splits into two disconnected components. Without loss of generality, suppose that $v_1$ lies in one component and $v_2,v_3$ in the other. Then $v_2\Rightarrow v_3 \rightarrow v_2$ and $u_1\Rightarrow u_2 \rightarrow v_1 \rightarrow u_1$ are disjoint cycles.


*Finally, suppose that all components satisfy $|V_i|\le 2$. There must exist at least four components such that $|V_i|=2$, say $|V_1|=|V_2|=|V_3|=|V_4|=2$. Let their respective intersection points be $\{v_1(i),v_2(i)\}$ for $i=1,2,3,4$. We will say that $V_i$ splits $V_j$ if $v_1(j)$ and $v_2(j)$ lies within distinct connected components of $C\backslash\{v_1(i),v_2(i)\}$. Note that this relation is symmetric. If there exists indices $i,j \in \{1,2,3,4\}$ such that $V_i$ and $V_j$ are not split, then we have disjoint cycles $v_1(i) \rightarrow v_2(i) \Rightarrow v_1(i)$ and $v_1(j) \rightarrow v_2(j) \Rightarrow v_1(j)$. So suppose that $V_i$ and $V_j$ are split for all $i,j$. Then without loss of generality, we can write the ordering of the vertices in $C$ as $$C=v_1(1)\rightarrow v_1(2) \rightarrow v_1(3) \rightarrow v_1(4) \rightarrow v_2(1) \rightarrow v_2(2) \rightarrow v_2(3) \rightarrow v_2(4) \rightarrow v_1(1).$$
In this case, the disjoint cycles are given by $v_1(1) \Rightarrow v_1(2) \Rightarrow v_2(2) \rightarrow v_2(1) \Rightarrow v_1(1)$ and $v_1(3)\rightarrow v_1(4) \Rightarrow v_2(4) \rightarrow v_2(3) \Rightarrow v_1(3)$.
