Coupon Accepted Successfully!


Bridge or Cut Edge


On removing an edge from a graph, the number of connected components of the graph either remains unchanged or it increases by exactly 1. So, an edge e of a graph G is called bridge or cut edge, if the subgraph G=e has more connected components than G has.

Theorem 1 :

Let e be an edge of the graph G and, as usual let G-e be the subgraph obtained by deleting e.

Then 523.png

where ω(a) is number of connected components of G.

Theorem 2 :

An edge e of a grpah G is a bridge if e is not a part of any cycle in G.

Theorem 3 :

Let G be a graph with n vertices, and q edges and, let ω(G) denote number of connected components of G. Then G has at least n-ω(G) edges, i.e. q  n-ω(G)

Corollary : A graph with
 n vertices less than (n – 1) edges can not be connected.

Theorem 4 :

Let G be a graph with n vertices, then following three statements are equivalent.

I. G is tree

II. G is an acyclic graph with (n – 1) edges.

III. G is a connected graph with (n – 1) edges.

Test Your Skills Now!
Take a Quiz now
Reviewer Name