In a connected graph, a bridge is an edge whose removal disconnects the 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 bridge in a graph is incident on a cut vertex. D. A graph with bridges cannot have a cycle.

GATE 2015 · Discrete Mathematics · Graph Connectivity · medium

Answer: B. A bridge cannot be part of a simple cycle.

1. Evaluate option A: A tree is acyclic, so EVERY edge lies on no cycle — every edge of a tree is a bridge. Option A ('A tree has no bridges') is FALSE.
2. Evaluate option B: By the bridge-cycle criterion, if edge e lies on a simple cycle, then e is NOT a bridge (removing it leaves alternate paths). Conversely, a bridge cannot lie on any cycle. Option B is TRUE.
3. Evaluate option C: A bridge connecting to a leaf vertex: the leaf has degree 1 and is not a cut vertex, yet the edge is a bridge. Example: path 1-2-3, edge (1,2) is a bridge but vertex 1 is a leaf (not a cut vertex). Option C is FALSE.
4. Evaluate option D: A graph can have both cycles and bridges. Example: two triangles connected by a single edge — the connecting edge is a bridge, yet both triangles are cycles. Option D is FALSE.