-
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 bridge
- A bridge cannot be part of a simple cycle
- Every edge of a clique with size ³ 3 is a bridge (A clique is any complete subgraph of a graph
- A graph with bridge cannot have a cycle
- A tree has no bridge
Correct Option: B
Since, every edge in a tree is bridge
∴ (a) is false Since, every edge in a complete graph kn (n ≥ 3) is not a bridge
⇒ (c) is false
Let us consider the following graph G :
This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (d) is false Since, in a cycle every edge is not a bridge
∴ (b) is true
