Prove that a edge-modified graph G' is connected if G contains a circuit

Question

The following question was on my Discrete Math practice final:

Let $G$ be a simple connected graph and $C$ a circuit. Let edge $e$ be in $C$. Prove that $H$ = $G-e$ = $(V, E-{e})$ by deleting $e$ must also be connected.

The way I approached this problem was proof by contradiction (so perhaps I could get my hands on a concrete object).

I started by assuming the hypothesis and that the new graph (after removing $e$), $H$, was disconnected.

$H$ being disconnected means that there exists a pair of vertices $(u,v)$ in H where no path (sequence of edges) $P$ exists connecting $u$ and $v$. $H$ being disconnected also implies that $H$ has at least 2 connected components.

My next ideas were as follows: removing any one edge $e$ from a circuit $C$ doesn't disconnected the circuit, since 1) any vertices in $C$ NOT endpoints of $e$ haven't been affected and are thus still have paths between them, and 2) if $u$ and $v$ are endpoints of $e$, the deletion of $e$ doesn't affect connectivity because there is a path P from $u$ to $v$ - namely, using edges that go through the remaining vertices.

Using this fact, I thought I could come up with a contradiction: Since $e$, by contradictory assumption is a cut-edge, its removal disconnects $G$ into two disjoint components. Since $e$ was in $C$, the removal of $e$ should have disconnected $C$, where one part of it is in a connected component and the other part is in another. But since $C$ is a circuit, the removal of any edge in $C$ can't disconnect it. So therefore we have a contradiction, and thus the original claim is true - namely, the new graph H must also be connected.

I'm pretty sure my proof sketch is wrong, but I would definitely like some feedback and explanation. Thanks!

Answer 1

No your proof is correct although a bit overcomplicated (mostly terminologically) in one of the paragraphs -- but the fact you are proving is very simple and can be explained in many ways.

The simplest way to do that, though, would be saying that since deleting $e = ab$ doesn't even disconnect $a$ from $b$ (as you correctly wrote above, removing $e$ doesn't affect connectivity of the circuit $C$) then what else could it have disconnected? Or a bit more formally, if shortest path $P$ from $u$ to $v$ in $G$ doesn't have edge $e$ in it then $P$ lies in $H$ as well. And if $P$ contains $e$ (no more than once!) then you can always replace $e$ with $C\backslash e$ and thus produce path $P'$ that still connects $u$ and $v$ and lies completely within graph $H$.