Cut Edges and Cut Vertices

From DocR21

A vertex v is called a cut vertex of the graph G if removing the vertex v and the boundary edges from G results in more components than G. An edge e is called a cut edge of the graph G if removing the edge e from G results in more components than G. When an edge is removed from a graph, its vertices are left in. Vertices C, D, E, and G are cut vertices of the graph in the following figure, because removing them from the graph results in more components.

The top of the following figure shows what happens when vertex E is cut from the graph, resulting in two components. Likewise, edges D-E and E-G are cut edges of the graph. The bottom of the following figure shows what happens when edge E-G is cut from the graph, resulting in two components. Vertices A, B, C, D, E, G, H, and I are cycle vertices of the graph depicted in the following figure.

Class methods from generic_graph associated with cut vertices and edges include generic_graph::cut_vertices(), generic_graph::is_cut_vertex(), generic_graph::cut_edges(), and generic_graph::is_cut_edge. Scheme extensions include graph:cut-vertices, graph:cut-vertex?, graph:cut-edges, and graph:cut-edge?.