Graph Theory – Proving an Edge is in a Cycle if Not a Cut Edge

discrete mathematicsgraph theoryproof-verification

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?

Best Answer

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

Related Question