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.
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:
- Is the idea of the first half of the proof missing any ideas?
- How can I move forward with the second half?