Suppose G is a connected undirected graph. An edge e whose removal disconnects t

Question

Suppose G is a connected undirected graph. An edge e whose removal disconnects the graph is called a bridge. Must every bridge e be an edge in a depth-first search tree of G? Give a proof or a counterexample.

Explanation / Answer

I think that the bridge is an edge whose end vertex is a cut node, because cut node removal disconnects the graph so removing that edge will also disconnect the graph. This is not exact. Particularly, if you read it as (bridge => edge has a cut node), that is true. But phrased as "a bridge is an edge whose end vertex...", it suggests the converse implication, which is not true. All in all, this sentence is largely irrelevant for the rest of the argument and I'd just omit it. ... only tree edges can be cut edges ( or bridges ) because back edge removal doesn't disconnect the graph. Yeah, that's it. Plus you have to note that DFS explores all vertices (or labels all edges) of a connected graph.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.