The Gateway to Computer Science Excellence
+36 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
in Graph Theory by Veteran (106k points)
edited by | 3.7k views

Reason why D is not the answer

They are asking for "True" and Option D is FALSE, counter example of option D is ur figure.
Why u r confused ?
sorry,my mistake

Edited the comment
Plz, Never edit any comment in between. Otherwise, whole discussion makes no sense to future readers. :)
that is the most logical should be in rule book of GO

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.

3 Answers

+26 votes
Best answer

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$

by Loyal (8k points)
edited by

A clique, C, in an undirected graph G = (VE) is a subset of the verticesC ⊆ 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


This might help .... 


This one ....

+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.
by Boss (13.7k points)
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.

+5 votes
Ans B- bridge cannot be part of a simple cycle
by (281 points)
y not A & B both beacuse tree is acyclic connected graph & tree can never bridge so it shd also true


kindly explain
tree is minimally connected means removal of any vertex or edge graph becomes disconnected. Every vertex is cut vertex and every edge is cut edge..

So A is false..

Leaves of the tree are not the cut vertex.


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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,700 answers
107,475 users