edited by
14,505 views
48 votes
48 votes

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

  1. A tree has no bridges
  2. A bridge cannot be part of a simple cycle
  3. Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph)
  4. A graph with bridges cannot have cycle
edited by

4 Answers

Best answer
39 votes
39 votes

Bridge / cut edge : A single edge whose removal will disconnect the graph is known as Bridge or cut edge.

  1. Every edge of a tree is a bridge.
  2. A bridge cannot be a part of a single cycle because in a cycle every vertex will be connected with every other vertex in $2$ ways. Even if you remove $1$ way by deleting an edge still the other way will make sure that the graph is connected.
  3. A Clique will never have a bridge because though we remove $1$ edge between any $2$ vertices those $2$ vertices will still be connected with the remaining $(n-2)$ vertices using an edge each.
  4. Red edge in the below graph is clearly a bridge as removing that will produce an isolated vertex.

Correct Answer: $B$

edited by
38 votes
38 votes
Ans B

In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle.
5 votes
5 votes
Ans B- bridge cannot be part of a simple cycle
0 votes
0 votes

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

Answer:

Related questions

28 votes
28 votes
6 answers
1
go_editor asked Feb 12, 2015
12,725 views
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ isA multiple of 4EvenOddCongruent to 0 $mod$ 4...
26 votes
26 votes
5 answers
3
go_editor asked Feb 12, 2015
14,093 views
Consider the following routing table at an IP router:$$\begin{array}{|l|l|l|} \hline \textbf {Network No} & \textbf {Net Mask} & \textbf{Next Hop} \\\hline \text {128.96...