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.





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