4
$\begingroup$

Just need help proving the statement below, for which I've outline how the proof would go:

Theorem: An edge $e$ of a graph $G$ is a bridge iff $e$ lies on no cycle of $G$

Attempt $(\implies)$

Assume for the sake of contradiction that there exists a bridge $e$ in the edge set of $G$, such that $e$ lies on a cycle. Then, if we take a simple case such as $C_{3}$, we arrive at $P_{3}$, which is connected. This is a contradiction, and so there cannot exist an edge $e$ such that $e$ is a bridge that lies on a cycle.

Attempt $(\impliedby)$

Let $e$ be any edge such that $e$ lies on a cycle, $C_{n}$. Then, let us remove $e$ from the edge set of $C_{n}$. By definition of a cycle (a closed path) we know that the removal of any single edge in the cycle creates a path $P_{n}$. A path is connected, and so we arrive at the conclusion that the removal of any single edge is not enough to disconnect a cycle.

Any feedback would be great!

$\endgroup$
3
$\begingroup$

You need to be a bit more precise IMHO. Introduce notation.. Let $e$ be an edge that is a bridge and suppose it lies on a cycle $C$. So let $C$ consist of points $x_0,\ldots,x_n, x_{n+1} = x_0$ such that $(x_i, x_{i+1})$ are edges of $G$ for all $i =0, \ldots n$. We can suppose WLOG (renumbering if needed) that $e$ is the edge $(x_n, x_0)$. If we remove $e$ from the graph, the number of connected components must increase, and the only component $G'$ of $G$ that could get split is the one containing $e$, but it's easy to see it does not get split, but stays connected: if there was a path between two points $p,q$ in $G'$ that contained $e$, then we still have a path without it, just take the route $x_0 \to \ldots \to x_n \to x_n$ instead of $e$. So $e$ is not a bridge: contradiction.

Essentially the same argument proves the converse as well: a single edge on a cycle can always be replaced by the rest of the cycle.

$\endgroup$
3
$\begingroup$

Proof by contradiction. Suppose $e$ is a bridge of $G$ and on a cycle of $G$. By removing $e$, we know there is a path between two vertices of $e$. Which this is contradicted by definition of bridge ($\Rightarrow$).

Now, suppose $e$ lies on no cycle in $G$. Remove $e$ from $G$, and we suppose there is a path between vertices of $e$ after removing $e$, as $e$ is not a bridge. Now, add $e$ again. As there is a path between two vertices of $e$ which is not through $e$, there is a cycle in $G$ which is passed through $e$. Which is contradicted by $e$ is not a bridge. Therefore, $e$ is a bridge of $G$ ($\Leftarrow$).

$\endgroup$

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.