3.1. Cut-vertices, bridges, and blocks

A vertex v of a graph G is called a cut-vertex of G if .

Theorem 3.1. A vertex v of a graph G is a cut-vertex iff there exist vertices u and w - both are different from v - such that v is on every path of G.

Proof. It suffices to prove the theorem for connected graphs.

- Let v be a cut-vertex of G. Then the graph is disconnected.

If u and w are vertices in different components of , then there are no paths in . However, since G is connected, there are paths in G. Therefore, every path of G contains v.

 

- Assume that there exist vertices u and w in G such that the vertex v lies on every path of G. Then there are no paths in , implying that is disconnected and that v is a cut-vertex of G.

Theorem 3.2.: Every nontrivial connected graph contains at least two vertices that are not cut-vertices.

Proof. Let us suppose that the theorem false. Then there exists a nontrivial connected graph containing at most one vertex that is not a cut-vertex. This means that every vertex of G, with at most one exception, is a cut-vertex.

Let u and v be vertices of G such that . At least one of u and v is a cut-vertex, say v. Let w be a vertex belonging to a component of not containing u.

Since every path in G contains v, we conclude that , which is a contradiction.

A bridge of a graph G is an edge e such that .

There are some simple statements for which the proofs remain to the reader.

Statement 3.3. If e is a bridge then .

Statement 3.4. If then u is a cut-vertex of G iff .

Statement 3.5. The complete graph K2 is the only connected graph containing a bridge but no cut-vertex.

A cycle edge is an edge that lies on a cycle. A bridge incident with an end-vertex is called a pendant edge. A nontrivial connected graph with no cut-vertices is called a nonseparable graph. A maximal nonseparable subgraph of G is called a block.

Figure 3.1. A graph and its 5 blocks

An internal vertex of a u-v path P is any vertex of P different from u or v. A set of paths, , is called internally disjoint if each internal vertex of , , lies on no path, . In particular, two paths are internally disjoint if they have no vertices in common, other than u and v. Similarly, edge-disjoint paths have no edges in common.