About MATtours
Site mapGallery of graphs and algorithmsHow to teach using investigationsClickable list of termsHelp

Disconnections: bridge, cut vertex, block

When a connected graph can become disconnected by removing a single edge, that edge is called a bridge. A graph can contain more than one bridge. The edge-connectivity of a graph with a bridge is always 1.

graphs with bridges
Each of these graphs contains at least one bridge. Note that if a graph has a bridge, there will always be at least one pair of vertices such that the bridge is contained in every path between them.

When the removal of a single vertex causes a graph to become disconnected, that vertex is called a cut vertex. The vertex connectivity of a graph with a cut vertex is always 1. A graph can have more than one cut vertex.

vertex connectivity equals 1
Each of these graphs contains at least one cut vertex.

A nontrivial connected graph with no cut vertices is called a block. A block of a graph is a maximal subgraph which is itself a block.

Some graphs and their blocks:

graphs and blocks

Copyright © 1999-2000 SciMathMN