Existence of an edge that is contained in at least two cycles

Question

Let $G$ be a graph with $n$ vertices and $\geq \frac{3n}{2}$ edges. Prove that there exists an edge in $G$ that is contained in at least two different cycles.

My approach: Consider $G$. Pick a random edge. Let $X(e)$ be the number of cycles that contain $e$. Somehow show that $E[X] > 1$. Then there exists an $e$ such that $X(e) \geq 2$.

Does this probabilistic method approach work?

Edit: I would like to add that for a graph $G$ with $n$ vertices and $m$ edges, one can find an edge that is present in multiple cycles, or identify if there is none, in $O(m^2(m+n))$ time with multiple DFS's.

Answer 1

Let $G$ have $E$ edges and $k$ components and suppose that no edge is in two distinct cycles.

The number of edges in a spanning forest $F$ for $G$ is $n-k$. Let $e$ be any of the remaining $E-n+k$ edges.

The graph formed by adding $e$ to $F$ must contain a cycle.This cycle must contain at least two edges of $F$. Since we can do this for each of the extra $E-n+k$ edges, we must have $$n-k\ge 2(E-n+k).$$

Then $E\le \frac{3(n-k)}{2}<\frac{3n}{2}$.

Answer 2

Suppose ever two cycles are edge disjunct and suppose these cycles are $C_1,C_2,...C_k$. Then $$|C_1 |+...+|C_k|\leq \varepsilon$$ and since each cycle has at least $3$ edges we have $3k\leq \varepsilon$.

Let $F$ be spanned forest in $G$. Then each edge in $G\setminus F$ lies in exactly one cycle and each cycle contains exactly one edge in $G\setminus F$, so we have $k\geq \varepsilon -(n-1)$. So we have $$3\varepsilon -3(n-1)\leq \varepsilon \implies \varepsilon \leq {3n-3\over2}$$

A contradiction.