1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.