GATE CS 2015 Set 2 Q.60 (CS Q.50): Graph Theory

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?

A tree has no bridges

A bridge cannot be part of a simple cycle

Every edge of a clique with size $\ge 3$ is a bridge (A clique is any complete subgraph of a graph)

A graph with bridges cannot have a cycle

Official answer and solution

Solution

Apply the fundamental theorem connecting cut-edges (bridges) and cycles in graph theory.

Theorem: An edge $e = (u, v)$ in a connected graph $G$ is a bridge if and only if $e$ is not contained in any simple cycle of $G$ .

Proof sketch:

If $e$ lies on a simple cycle $C$ , then removing $e$ leaves the remainder of the cycle $C \setminus \{e\}$ , which provides an alternative path between $u$ and $v$ . Thus, $G - e$ remains connected, so $e$ cannot be a bridge.
Conversely, if $e$ is not part of any cycle, there is no alternative path between $u$ and $v$ , so removing $e$ disconnects $G$ .

Evaluating the choices:

(A) Every edge in a tree is a bridge. False.
(B) 'A bridge cannot be part of a simple cycle' is precisely the definition/theorem. True.
(C) Cliques of size $\ge 3$ are 2-edge-connected and contain no bridges. False.
(D) A graph can easily have both cycles and bridges (e.g., two triangles connected by a single bridging edge). False.

Final answer

Common trap

Believing trees have no bridges when in fact every edge of a tree is a bridge.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.