1
$\begingroup$

$B$ is a nonseparable subgraph of $G$ that is not a proper subgraph of any other noseparable subgraph of $G$. Show that any two egdes of $e$ and $f$ lie on a common cycle of $G$.


Let $C$ be a cycle containing $e$ (every edge lies on some cycle since there are no bridges in a nonseparable graph) We must assume $f$ is not on $C$, otherwise the proof is complete.

There exists some path $P=(u=u_0, ...u_k=v)$ in $B$ such that all but one vertices, say $v$, lie on $C$ and $f=u_0u_1$.

Don't know what to do next, can I form a path from $u_0$ to another vertex on the cycle, not containing any other vertices in $P$?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Following on from my working above, with the helpful comment by N8tron...

Since $v=u_k$ is not a cut-vertex, there exists a path from $u$ along $P-u_k$ to some other vertex, say $w$, on $C$ in $B-u_k$, where no other vertex of this path intersects the cycle other than the end-vertex $w$.

So $u_{k-1}$ is adjacent to $v=u_k$ and is connected to $w$ (via an internally-disjoint path). Therefore, the path along $C$ from $v$ to $w$ containing $e$ together with the $v-w$ path via $u_{k-1}$, not containing $e$ forms another cycle - which has a smaller path $u_0, ..., u_{k-1}$ attached (to one vertex). We may repeat this until all remaining edges in the remaining path are in a cycle together with $e$. So $e$ and $f$ reside on a common cycle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .