# Prove that an edge $e$ is contained in a cycle iff $e$ is not a cut edge in a simple graph $G$.

I am trying to finish up a proof and I'm struggling to put my ideas into words more than trying to figure out what's going on.

I have the following proof template outline for this proof.

Proof.
Let $e$ be an edge of a graph $G$.
$\Rightarrow$ Suppose that $e$ is contained in a cycle.
...
Therefore $e$ is not a cut edge in $G$.
$\Leftarrow$ On the other hand, suppose $e$ is not a cut edge in $G$.
...
Therefore $e$ is contained in a cycle.

I'm currently learning about trees, but I don't think I can apply any of those properties because G is not necessarily even connected.

For the first part of the proof, here's my thinking - take a component of $G$ that contains a cycle, we'll call this component $H$. Remove $e$ from the cycle. Since $H$ is a cycle, $H - e$ is still connected, so you don't have any less components in $H - e$, and thus no fewer components in $G - e$. Therefore $e$ is not a cut edge in $G$. Am I missing anything?

For the second part of the proof, I'm having a lot of trouble putting my thinking into words. Maybe I'm being afraid of simplicity. Here's my thinking - we know that $e$ is not a cut edge, which means that removing e will not change how many components G has. Removing an edge in any other circumstance will change the components of G. This is where I'm stuck. I don't think I'm explaining enough.

So really, two main questions:

1. Is the idea of the first half of the proof missing any ideas?
2. How can I move forward with the second half?

Your first argument is basically fine, but you should probably say a little more about why $H-e$ is still connected (unless you’ve already proved that removing an edge from a cycle does not disconnect the component).
I would approach the other direction differently. Instead of trying to prove that if $e$ is not a cut edge, then $e$ is contained in a cycle, I would try to prove the (logically equivalent) contrapositive: if $e$ is not contained in a cycle, then $e$ is a cut edge. HINT: Suppose that $e$ is not contained in a cycle, and let $u$ and $v$ be the vertices at which $e$ is incident. Show that $u$ and $v$ are in distinct components of $G-e$.
• Excellent! Thanks! I understand the second part much better now. Can you elaborate on one more thing, then - how could I show that $H - e$ is still connected? Would I use a path in that cycle? A better option? – Dewick47 Apr 6 '16 at 1:16
• @dewick49: You’re welcome! Yes, use the fact that you can always go round (what’s left of) the cycle the other way, so that any path that used $e$ can be replaced by the rest of the cycle in reverse order. – Brian M. Scott Apr 6 '16 at 1:18