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!


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

| cite | improve this answer | |

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.