11,863 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 a tree every edge is a BRIDGE

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

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

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$

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

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.

Ans B

In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle.

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.

Ans B- bridge cannot be part of a simple cycle
by

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

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

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