28.1.1. Vertex and Edge Connectivity

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. So, remember 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.

A vertex cut is a specific set of vertices in a graph whose removal results in the graph being disconnected. In simpler terms, if you remove certain nodes (vertices) from a graph, and the remaining part of the graph cannot reach some parts of the original graph, those removed nodes are a vertex cut. An articulation point is a single vertex that, when removed, increases the number of connected components of the graph. It is a clear example of a vertex cut.

Think of a city connected by roads (a graph). If a certain highway (a vertex) is closed for repairs, and as a result, you cannot reach part of the city (disconnected graph), then that highway is a vertex cut.

So, now let us next define vertex connectivity of a graph. And the vertex connectivity of a graph is also denoted by this parameter kappa, κ(G). So, the vertex connectivity of a graph is the size of the smallest vertex cut. That means the size of the smallest V’ whose deletion will disconnect your graph or equivalently it is the minimum number of vertices to be deleted to disconnect your graph.

Vertex connectivity, represented as κ(G), quantifies how 'robust' a graph is regarding its vertices. It is determined by finding the smallest set of vertices (the vertex cut) that can be removed to make the graph disconnected. For example, if you need to remove two specific nodes to disconnect the graph, the vertex connectivity is 2.

Imagine a power grid where the nodes represent substations. The vertex connectivity would indicate the minimum number of substations that need to be taken out of service to cause some regions to lose power. If two substations must be taken out to isolate a part of the grid, the vertex connectivity is 2.

So, if you take a complete graph of n nodes even if you remove up to n - 1 nodes, your graph still remains connected, the reduced graph. So, remember my V’ ⊆ V. You cannot say that you can delete the entire graph itself because if you delete the entire set of vertices the entire graph vanishes.

A complete graph is one where every vertex is connected to every other vertex. The vertex connectivity here is interesting because, no matter how many vertices you remove, as long as at least one vertex remains, the graph remains connected. Therefore, for complete graphs, the highest possible vertex connectivity is n - 1, where n is the total number of vertices.

Consider a fully interconnected social network. If each person (vertex) is friends with everyone else, taking out one or even 100 friends won't disconnect any individual. The network remains intact as long as one person is left.

So, we now define what we call as an edge cut. So, imagine you are given a graph and a collection of edges E’ will be called an edge cut, if deleting the edges in E’ from the graph G disconnects your graph.

An edge cut refers to a set of edges whose removal disconnects the graph. The focus here is less on the size of the cut and more on whether the removal successfully splits the graph into two or more disconnected pieces. Specific edges can act as conduits or bridges between different parts of the graph.

Think of a water supply network. If certain pipes (edges) are blocked, and that blockage causes some houses (nodes) to lose water supply, those pipes represent an edge cut.

So, we now define what we call as the edge connectivity of a graph and this is denoted by λ. So, what is the edge connectivity of a graph? It is the size of the smallest edge cut or equivalently the minimum number of edges to be deleted which disconnects the graph.

Edge connectivity, denoted as λ, measures the minimum number of edges required to remove in order to disconnect the graph. It is determined through the smallest set of edges (edge cut) that must be removed to isolate vertices. This concept helps analyze the resilience of the graph against edge failures.

Consider a communication network where links (edges) connect multiple stations (nodes). The edge connectivity tells us how many links can be cut before a station loses communication with the network entirely. If two connections must be cut to isolate one, the edge connectivity is 2.

So, we want to establish a relationship between the vertex connectivity and edge connectivity. And there is a very nice theorem statement which says that you take any connected, non-complete graph then the vertex connectivity is always less than equal to the edge connectivity.

The theorem states that for connected, non-complete graphs, the vertex connectivity (κ) will always be less than or equal to the edge connectivity (λ). This means that the minimum number of vertex deletions needed to disconnect the graph is less than or equal to the minimum number of edge deletions needed to achieve the same effect. This relationship helps in analyzing the overall connectivity strategy for networks.

In terms of highway systems, this means that removing a certain minimum number of intersections (vertices) can disconnect a city more easily than removing streets (edges). If you can isolate a city by shutting down fewer intersections than streets, it highlights the importance of those key connection points in the network.

--