If $|E(G)| \geq |V(G)| +4,$ then G contains two edge-disjoint cycles

Question

This exercise is on the book Graph theory with Application by Bonty and Murty (1.7.6). I'm studying for a final test and I can't complete this prove.

I know how to do construct that graph but I don't know if that proves it for all the cases.

Answer 1

We can begin by making a few simplifications.

1. If $|E(G)| > |V(G)| + 4$, we can delete the extra edges to get a graph $G'$ with $|E(G')| = |V(G')|+4$. If there are two edge-disjoint cycles in $G'$, they still exist in $G$. So we can assume that equality holds.

2. If $G$ has a vertex of degree $1$, then we can delete that vertex and the edge out of it. The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $2$.

3. Similarly, if $G$ has a vertex of degree $2$, then we can delete that vertex and the edges out of it, but connect its neighbors by an edge directly. (This might create a multigraph out of a simple graph.) The resulting graph $G'$ still has $|E(G')| = |V(G')| + 4$, so we can try to prove $G'$ has two edge-disjoint cycles, which give two edge-disjoint cycles in $G$. By applying this repeatedly, we get to assume that $G$ has minimum degree $3$.

In a graph with minimum degree $3$, $|E(G)| \ge \frac32 |V(G)|$; when $|E(G)| = |V(G)|+4$, we conclude that $|V(G)| + 4 \ge \frac32 |V(G)|$, so $|V(G)| \le 8$.

If $G$ has no cycles of length $4$ or shorter (which means in particular that it has no cycles of length $1$ or $2$, so it is a simple graph), then take an arbitrary vertex $v$ and three of its neighbors $w_1, w_2, w_3$; those neighbors must have at least $6$ more neighbors of their own, distinct from each other and from $v$, giving us at least $10$ vertices, contradicting $|V(G)| \le 8$.

But if $G$ has a cycle of length $4$ or shorter, then we can delete all edges in that cycle; the remaining graph $G'$ still has $|E(G')| \ge |V(G')|$, so it contains a second cycle, which is disjoint from the first. This gives us two edge-disjoint cycles in $G$, completing the proof.