# 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

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.