The Gateway to Computer Science Excellence
+32 votes
3.2k views

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 (105k points)
edited by | 3.2k views
+14

Reason why D is not the answer

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

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

In a tree every edge is a BRIDGE

0
Yes please don't edit the comments.

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

3 Answers

+23 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 (7.9k points)
edited by
0

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

0

This might help .... 

0

This one ....

+37 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.5k points)
0
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 .
+1
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
0

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)
0
y not A & B both beacuse tree is acyclic connected graph & tree can never bridge so it shd also true

 

kindly explain
+10
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..
+3

Leaves of the tree are not the cut vertex.

+4

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

@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,645 questions
56,586 answers
195,787 comments
101,836 users