2
$\begingroup$

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?
$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dewick47 Apr 6 '16 at 1:16
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 6 '16 at 1:18

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.