The following is my attempt at proving the theorem stated in the question. Is it correct? I am a bit iffy about the logic in the first paragraph… Thanks in advance.
Proof.
We first show that an edge is a bridge if it does not lie on a cycle. Assume not, so that the edge $e$ is a bridge, but does lie on a cycle. Consider the endpoints $u$ and $v$ of $e$. Remove $e$ from $G$. By assumption, $u$ and $v$ are disconnected, since $e$ is a bridge. But, $e$ lies on a cycle, and so $u$ can be reached from $v$ (and vice versa) by following the cycle in the opposite direction of $e$; hence $u$ and $v$ are not disconnected when $e$ is removed, a contradiction since $e$ is a bridge.
It remains to be shown that if an edge does not lie on a cycle, then it is a bridge. Consider again an edge $e = \{u, v\}$ that does not lie on a cycle. Since $e$ does not lie on a cycle, there must be no other path connecting $u$ and $v$ in a $P$, otherwise $e$ would lie on a cycle. In this case, the removal of $e$ from $G$ must disconnect $u$ and $v$ in $G$. Hence, $e$ is a bridge. The theorem follows by combining both directions of the implication.
Best Answer
Your second section shows the logic that if an edge does not lie on a cycle, then it is a bridge, which is fine. This means your first section needed to show the reverse direction: if edge is bridge, then it does not lie on a cycle. So the statement you started off with: "We first show that an edge is a bridge if it does not lie on a cycle" is incorrect. You should instead show that an edge does not lie on a cycle if an edge is a bridge. Which means, if you want to prove by contradiction again, you should start off with: assume for contradiction, that an edge is a bridge and it lies on a cycle... This is quite weird as we're going backwards to fix your first section, and this is because we are keeping the second paragraph. Your first and second graphs both have correct logic but they are proving the same logic statement instead of both directions.