Proofing properties about bridges in trees

Question

I'm looking at these two problems:

Ex 5.5.1 Suppose that $G$ is a connected graph, and that every spanning tree contains edge $e$. Show that $e$ is a bridge.

Ex 5.5.2 Show that every edge in a tree is a bridge.

(source)

We call an edge in a graph $G$ a bridge if the removal of the edge would disconnect $G$.

The argument for both problems seems kind of similar. As we talk about acyclic, connected graphs - namely trees - in both questions.

If we define that every two nodes in a tree are joined by a unique path as a lemma, we should be able to use the same proof for both problems:

In a tree $T$, there is a unique path $P$ between any two vertices $u, v$. Since $P$ is unique, removing any edge $e$ from $P$ necessarily disconnects the components containing $u$ and $v$. Hence $e$ must be a bridge, as its removal disconnects $T$.

Does this make sense or did I think too simple?

Answer 1

Since $P$ is unique, removing any edge $e$ from $P$ necessarily disconnects the components containing $u$ and $v$

This assertion begs the question. This is precisely the same thing as what you’ve been asked to prove, so you can’t use it as a lemma.

I would recommend approaching the problem by contradiction. Assume that removing $e$ doesn’t disconnect the graph, and prove that there is a spanning tree that doesn’t include $e$.

You’re right that the second exercise follows from the first immediately, though you should write a sentence explaining why. I don’t understand your explanation for why they’re the same... certainly we aren’t assuming $G$ is acyclic in the first exercise!

Answer 2

Your argument works for 5.5.2. For 5.5.1, assume $e$ is not a bridge and find a spanning tree of $G-e$.