In a **tree **every edge is a **BRIDGE**

Dark Mode

11,142 views

46 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

38 votes

Best answer

**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$

**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

**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

5 votes

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

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