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? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle Graph Theory gatecse-2015-set2 graph-theory graph-connectivity easy + – go_editor asked Feb 13, 2015 edited May 27, 2018 by kenzou go_editor 14.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments register_user_19 commented Oct 29, 2019 reply Follow Share In a tree every edge is a BRIDGE 7 votes 7 votes `JEET commented Oct 29, 2019 reply Follow Share Yes please don't edit the comments. or write PS, so it can be referred to later. 0 votes 0 votes Abhrajyoti00 commented Jul 23, 2022 reply Follow Share A helpful video to understand about clique What is a Clique? | Graph Theory, Cliques - YouTube 1 votes 1 votes Please log in or register to add a comment.
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. Every edge of a tree is a bridge. 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. 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. Red edge in the below graph is clearly a bridge as removing that will produce an isolated vertex. Correct Answer: $B$ Vicky rix answered Sep 13, 2017 edited May 10, 2019 by Lakshman Bhaiya Vicky rix comment Share Follow See all 2 Comments See all 2 2 Comments reply set2018 commented Nov 13, 2017 reply Follow Share 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 0 votes 0 votes varunrajarathnam commented May 4, 2021 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
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. Vikrant Singh answered Feb 13, 2015 Vikrant Singh comment Share Follow See all 3 Comments See all 3 3 Comments reply radha gogia commented Jan 28, 2016 reply Follow Share 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 . 0 votes 0 votes saket nandan commented Aug 11, 2016 reply Follow Share 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 1 votes 1 votes Warrior commented Oct 15, 2017 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
5 votes 5 votes Ans B- bridge cannot be part of a simple cycle dkvg1892 answered Feb 17, 2015 dkvg1892 comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Warrior commented Oct 15, 2017 reply Follow Share @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. 5 votes 5 votes Gyanu commented Oct 31, 2019 reply Follow Share @Warrior 1st statement should be like this:- In a tree, every edge is cut edge and every vertex need not be a cut vertex. 1 votes 1 votes raja11sep commented Aug 30, 2021 reply Follow Share @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. 0 votes 0 votes Please log in or register to add a comment.
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 keshore muralidharan answered Aug 28, 2020 keshore muralidharan comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Aug 30, 2021 reply Follow Share @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”. 0 votes 0 votes Please log in or register to add a comment.