Connectivity, Cut Edge, and Cut Vertex¶

Connectivity¶

A graph G is connected if for every pair of vertices u and v, there exists a path from u to v. Otherwise, it is disconnected. Every disconnected graph is a collection of several connected graphs, each of which is called a component. Clearly, a connected graph has exactly one component.

If we imagine vertices as balls and edges as strings, the components of the graph can be physically separated by hand, but the vertices within each component remain connected by strings.

Cut Vertex¶

In graph G, a vertex v is called a cut vertex if removing it increases the number of connected components.

Cut Edge¶

In graph G, an edge e is called a cut edge if removing it increases the number of connected components.

k-Connected Graph¶

A graph G is called k-connected if it has more than k vertices and cannot be disconnected by removing x vertices (where x < k). The connectivity of G, denoted as \(\kappa (G)\), is defined as the maximum k for which G is k-connected. In other words, it is the minimum number of vertices whose removal disconnects the graph or reduces it to a single vertex.

Block¶

A block is a maximal subgraph of G that contains no cut vertices.