GATE CS 2015 Set 2 Q50 — Graphs: Connectivity, Matching, Colouring

An edge $e = (u, v)$ in a connected graph $G$ is a bridge (or cut-edge) if and only if its removal disconnects the graph. This is equivalent to saying that $e$ is not part of any cycle in $G$.

Let us evaluate each option:

• Option A: A tree has no bridges
  A tree on $n$ vertices has $n-1$ edges and no cycles. Removing any edge from a tree disconnects it into two separate components. Thus, every edge in a tree is a bridge. This statement is false.
• Option B: A bridge cannot be part of a simple cycle
  If an edge $e = (u, v)$ is part of a simple cycle, there exists an alternative path between $u$ and $v$ that does not use $e$. Consequently, removing $e$ does not disconnect $u$ and $v$, and the graph remains connected. Thus, a bridge can never belong to any cycle. This statement is true.
• Option C: Every edge of a clique with size $\geq 3$ is a bridge
  In a clique (complete subgraph) of size $\geq 3$, every edge is part of at least one triangle (a cycle of length 3). Since these edges lie on cycles, none of them can be a bridge. This statement is false.
• Option D: A graph with bridges cannot have cycle
  A graph can easily contain both bridges and cycles. For example, consider a triangle (cycle of length 3) connected to a single pendant vertex by an edge. The connecting edge is a bridge, yet the graph contains a cycle. This statement is false.