28.1.3. Vertex Connectivity of a Graph

So, let us start with the definition of a vertex cut. It is also called as a separating set. So, imagine you are given a graph G = (V, E). Then a proper subset V’ ⊆ V of the set of vertices is called the vertex cut if removing the vertices in V’ disconnect your graph.

A vertex cut is a collection of vertices whose removal will disconnect a graph. In simpler terms, if we have a graph that has various points (vertices) connected by lines (edges), identifying a vertex cut means finding a group of those points that, when removed, cause at least some of the remaining points to be unable to reach each other. This concept helps to understand weak points in a network where cuts can occur.

Imagine a city with several roads connecting neighborhoods. If certain critical roads (vertices) are blocked (removed), it can prevent people from traveling between neighborhoods, effectively 'disconnecting' them. A vertex cut, therefore, represents those critical roads.

If your graph has an articulation point, then that articulation point itself can constitute a V’ of potential V’ whose deletion will disconnect the graph. But, it might be possible that your graph may not have an articulation point in which case you may need to delete more than one vertex in the graph to disconnect it.

An articulation point is a single vertex whose removal increases the number of disconnected components of a graph. In graphs without such points, you may need to remove several vertices to achieve a disconnection. This concept illustrates the vulnerability of a graph's structure based on how points are connected.

Consider a power grid where certain transmission stations (vertices) are crucial. If one of these stations is removed, certain areas lose power (disconnect). However, in a less critical setup, disconnecting multiple smaller stations may be necessary to cause a significant outage.

The vertex connectivity of a graph is also denoted by the parameter kappa, κ(G). The vertex connectivity of a graph is the size of the smallest vertex cut. This means the size of the smallest V’ whose deletion will disconnect your graph.

Vertex connectivity (A(G)) quantifies the minimum number of vertices you must remove to disconnect the graph. For example, if a graph's vertex connectivity is 2, it indicates that you need to remove at least 2 vertices to disconnect the graph completely. This shows how robust or fragile a graph's connectivity is.

Think of a subway system: if you know that removing two key stations will make it impossible for commuters to travel from one side of the city to the other, then those stations are critical to the city's transport network's connectivity.

If your graph has an articulation point, then κ(G) will be 1. If no articulation point exists, you may need to delete multiple vertices. In graphs already disconnected, κ(G) is 0, meaning no additional deletions are necessary.

Various configurations of a graph lead to different values of vertex connectivity. In graphs with articulation points, you only need to worry about 1 vertex. In disconnected graphs, vertex connectivity is 0 since it's already separated.

Imagine a series of islands connected by bridges. If one bridge is critical (an articulation point), losing that bridge isolates an island. But if islands are already separate (disconnected), no bridges need to be 'cut' to ensure they stay isolated.

In complete graphs, you can't disconnect it by deleting fewer than n - 1 vertices, where n is the total number of vertices since they remain connected even if you remove multiple vertices.

Complete graphs are uniquely connected because every vertex is connected to every other vertex. Therefore, removing almost all vertices leaves at least one connection intact, maintaining connectivity until nearly all vertices are removed.

Visualize a fully connected social network where each person knows every other person. Even if you cut ties (remove people), as long as one person remains connected, the network stays intact until you've almost disconnected everyone.

--