Proofing properties about bridges in trees

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?

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!

• I don’t understand your explanation for why they’re the same... yeah I stated that not so clear.I didn't want to say that we can assume $G$ is acyclic, but that the spanning tree(s) of $G$ is acyclic, as it's also a tree. – Max Nov 22 '17 at 7:14
• @Max All edges of all trees satisfy the hypothesis of the first exercise. Just show that and that’s all you need (assuming you get the first one) – Stella Biderman Nov 22 '17 at 7:16
• I struggle a bit with coming up with the wording for the proof by contradiction (for 5.5.1): assume $e$ does not disconnect $G$ - then there is a spanning tree for the graph $G - e$, which contradicts the assumption that $e$ is included in all spanning trees of $G$. Does that make sense? – Max Nov 22 '17 at 7:23
• @Max Yes that makes perfect sense – Stella Biderman Nov 22 '17 at 7:24
• Thanks a lot for your help, can you give me a hint how you would state that 5.5.2 follows from 5.5.1? I only came up with something like: a tree is equal to its spanning tree. From 5.5.1 we know that an edge that appears in every spanning tree is a bridge. It follows that every edge in a tree has to be a bridge. – Max Nov 22 '17 at 7:33

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