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.
Best Answer
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}$.