in Graph Theory edited by
11,142 views
46 votes
46 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 edited by
11.1k views

4 Comments

In a tree every edge is a BRIDGE

6
6
Yes please don't edit the comments.

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

A helpful video to understand about clique  What is a Clique? | Graph Theory, Cliques - YouTube

0
0

4 Answers

38 votes
38 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$

edited by

2 Comments

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
0

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

3 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 .
0
0
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
1

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
1
5 votes
5 votes
Ans B- bridge cannot be part of a simple cycle

4 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.
5
5

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

@

  • 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
0
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

1 comment

 @

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
0
Answer:

Related questions