In a connected graph, a bridge is an edge whose removal disconnects a graph.…
GATE · 2015 · CS · Set 2 · Computer Science & IT
In a connected graph, a bridge is an edge whose removal disconnects a 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 edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)
- D.
A graph with bridges cannot have a cycle
Attempted by 323 students.
Sign up free to check your answer
Sign up freeLoading lesson…