# Proof of an edge $e$ of a graph $G$ being a bridge iff $e$ is not on a cycle of $G$

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!

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