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 simple terms, Clique is a complete graph found in another graph.

Ex:- Graph G = K4 + one vertex - connect this vertex with 2 edges with K4.

Therefore K4 is a clique in the above graph G.

 

In option C, they're saying that, every edge in that clique (no.of vertices in clique > 2) is bridge. - As we know, there are no bridges exist in any complete graph (n>2). - Hence, option C is wrong.

---

ahh that's great  explaination thnx !!

---

Option c 

explanation Here is the visual explanation for a clique of size \(n = 3\) (which is a simple triangle graph).A clique means every single corner (vertex) is directly connected to every other corner

Because removing the edge failed to disconnect the graph, that edge cannot be a bridge. This loop protection happens in every clique of size 3 or larger!

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.
 

---

nice explaination

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

opt a is false as consider a tree, now every edge acts as a bridge which means removing any edge disconnects the graph so a tree is full of bridges.

opt b A bridge cannot be part of a simple cycle is true because what is a bridge, removal of a bridge disconnects a graph , now in a cycle if we remove any edge then it wont disconnect the graph, so a bridge cannot be part of any cycle

opt c Every edge of a clique with size ≥3 is a bridge (A clique is any complete subgraph of a graph)

now what is a clique ???

==>> we have a graph, and we take a subgraph of that graph G and if that  subgraph itself is complete in nature, then that subgraph is a clique....

now we take a clique , we can also say it as a complete graph and if we remove any edge then also the graph remains connected.

opt d A graph with bridges cannot have cycle is false because in a cycle there can be no bridges but there can be a graph with cycles but bridges are there.

Answer 5

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”.