![GATE 2015 [Set-2]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
GATE 2015 [Set-2]
April 4, 2025STQC-NIELIT SC-B 2021
April 4, 2025GATE 2015 [Set-2]
|
Question 36
|
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 3 is a bridge (A clique is any complete sub graph of a graph)
|
|
|
A graph with bridges cannot have a cycle
|
Question 36 Explanation:
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
∴ (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
Correct Answer: B
Question 36 Explanation:
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
∴ (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