Prove if every 2 vertices are on a cycle, then every 2 edges are on a cycle

Question

I'm trying to prove the following:

Let $G$ be a connected graph of order at least 3 with no cut-vertices. Then, every pair of edges in $G$ lies on a common cycle.

My starting point is to use the fact that every pair of vertices of $G$ lies on a common cycle. This tells us that if $e = wx, f = yz$ are two edges in $G$, then, every pair of $w,x,y,z$ lies on a common cycle, but I'm getting stuck on showing that $e$ and $f$ are on a common cycle.

Any hints or tips?

Answer 1

The simplest argument is via the so-called Expansion Lemma:

If $G$ is a $k$-connected graph, and $G'$ is obtained from $G$ by adding a new vertex $y$ with at least $k$ neighbors in $G$, then $G'$ is $k$-connected.

In particular, if $G$ is $2$-connected (has no cut vertices) then this property is preserved when we add a vertex of degree $2$.

---

Start by proving the Expansion Lemma, if you do not have it already (for $k=2$ it is fairly easy). Then to find a cycle in $G$ containing edges $e$ and $f$, build a larger graph $G'$ with vertices $x$ and $y$ such that a cycle in $G'$ containing vertices $x$ and $y$ can be turned into a cycle in $G$ containing edges $e$ and $f$.