GATE CSE 2015 Set 2 | Question: 50

Question

In a connected graph, a bridge is an edge whose removal disconnects the 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 $\geq 3$ is a bridge (A clique is any complete subgraph of a graph)
• D. A graph with bridges cannot have cycle

Comments

In a tree every edge is a BRIDGE

---

Yes please don't edit the comments.

or write PS, so it can be referred to later.

---

A helpful video to understand about clique  What is a Clique? | Graph Theory, Cliques - YouTube

Answer 1

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

• A. Every edge of a tree is a bridge.
• B. 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.
• C. 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.
• D. Red edge in the below graph is clearly a bridge as removing that will produce an isolated vertex.

  

Correct Answer: $B$

Comments

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.

So it cant be disconnect the graph

---

Answer: (B)

Explanation: A bridge in a graph cannot be a part of cycle as removing it will not create a disconnected graph if there is a cycle.
 

Answer 2

Ans B

In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle.

Comments

Can you explain why option C is wrong , since it is a complete sub-graph so every edge will have to be removed so as to make the graph disconnected .

---

because in question it is saying that clique with edge >=3 , then take triangle which is complete subgrabph , if u will remove any edge from triangle then it will not devide the graph into components

---

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

Cut set: It is a set of edges whose removal makes the graph disconnected.

The option (c) is wrong because they are asking for Bridge not cut set .Don't confuse with the definition.

Answer 3

Ans B- bridge cannot be part of a simple cycle

Comments

@Hemant ,Yes u r right.

• Every vertex is cut vertex and every edge is need not be a cut edge.
•  Leaves of the tree are not the cut vertex.
• If a tree has only left or right subtree (but not both) then root and leaves are not the cut vertex.

---

@Warrior  1st statement should be like this:- In a tree, every edge is cut edge and every vertex need not be a cut vertex.

---

@Warrior

• If a tree has only left or right subtree (but not both) then root and leaves are not the cut vertex.

I didn’t get it. Anyone plz explain. 

Answer 4

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

Comments

 @keshore muralidharan

Since, in a cycle every edge is not a bridge.

In a cycle, every edge is not a bridge → there exists at least one edge in a cycle which is not a bridge.

But, the statement should be like “ None of the edges in a cycle is a bridge”.