In a connected graph, a bridge is an edge whose removal disconnects a graph.…
2015
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
- A.
A tree has no bridges
- B.
A bridge cannot be part of a simple cycle
- C.
Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)
- D.
A graph with bridges cannot have a cycle
Attempted by 177 students.
Show answer & explanation
Correct answer: B
Correct statement: A bridge cannot be part of a simple cycle.
Why:
If an edge belongs to a simple cycle, then after removing that edge the remaining edges of the cycle provide an alternate path between its endpoints, so the graph stays connected.
A bridge is an edge whose removal increases the number of connected components; therefore an edge on a cycle cannot be a bridge.
Quick checks of the other statements:
A tree: every edge is a bridge because there is exactly one path between any two vertices.
A clique with size ≥ 3: edges lie on cycles (triangles), so removing a single edge does not disconnect the clique.
A graph can have both bridges and cycles; presence of a cycle does not prevent other edges from being bridges.
A video solution is available for this question — log in and enroll to watch it.