0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – Max Nov 22 '17 at 7:14
  • $\begingroup$ @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) $\endgroup$ – Stella Biderman Nov 22 '17 at 7:16
  • $\begingroup$ 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? $\endgroup$ – Max Nov 22 '17 at 7:23
  • $\begingroup$ @Max Yes that makes perfect sense $\endgroup$ – Stella Biderman Nov 22 '17 at 7:24
  • $\begingroup$ 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. $\endgroup$ – Max Nov 22 '17 at 7:33
0
$\begingroup$

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

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