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.8k 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 Shimpy Goyal commented Jun 16, 2015 reply Follow Share y not A & B both beacuse tree is acyclic connected graph & tree can never bridge so it shd also true kindly explain 0 votes 0 votes Digvijay Pandey commented Jun 16, 2015 reply Follow Share 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.. 10 votes 10 votes Hemant Parihar commented Aug 12, 2017 reply Follow Share Leaves of the tree are not the cut vertex. 4 votes 4 votes 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.