28.1.7. Relationship Between Vertex Connectivity and Edge Connectivity

So, now let us define vertex connectivity of a graph. And the vertex connectivity of a graph is also denoted by this parameter kappa, $\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 Vertex connectivity refers to the least number of vertices that you need to remove from a graph to make it disconnected. If you think of a graph as a network where the vertices represent points and edges represent connections, vertex connectivity tells us how resilient that network is to failures.

For example, if a network has a vertex connectivity of 2, it means that at least two points must fail (i.e., be removed) to disrupt the entire network. This concept is essential for understanding the stability of networks, such as communication systems or transportation grids.

Consider a road network where intersections are the vertices and roads are the edges. If removing two specific intersections (vertices) leads to the entire area becoming disconnected, then the vertex connectivity of that road network is 2. If it takes removing just one intersection for some routes to become unusable, we can say that removing that intersection is critical for maintaining connectivity.

So, consider this graph and for this graph your $\kappa(G) = 2$. When $\kappa(G)$ will be 1 if your graph has an articulation point. But if there is no articulation point, you may need to delete more than one vertex to disconnect your graph.

In practical terms, graph examples help illustrate vertex connectivity clearer. Let's say we have a graph with different connection points. If the graph has an articulation point, it can be disconnected by removing that single point.

However, if there is not an articulation point, you would need to remove more than one point to achieve the same disconnection. This means that the graph has a higher vertex connectivity, which indicates a more robust network against single-point failures.

Think about a series of pipelines in a factory. If one pipe (vertex) can be removed, and the whole system shuts down, then that pipe is critical. But in a case where no single pipe is critical and you need to shut multiple pipelines to disrupt operations, it indicates a higher degree of interconnectedness and redundancy in the system.

Now we can keep similar theory with respect to a collection of edges whose removal will disconnect the graph. So, we 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.

Edge connectivity is analogous to vertex connectivity but focuses on the edges of the graph rather than the vertices. The idea is that if you can identify a set of edges whose removal leads to disconnection, then you are determining the robustness and resilience of the connections between the nodes.

Similar to vertices, there will be certain connections whose removal is critical to maintaining the overall flow or connection within the graph.

Consider a transportation system where each road represents an edge. If there are certain roads whose closure causes an area to be completely isolated from the rest, those roads are the edge cuts of that network. This is similar to how certain bridges or key highways, when closed, might limit traffic flow significantly.

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

This theorem establishes a boundary condition: that the resilience of a network in terms of vertex connectivity cannot exceed the edge connectivity. In simpler terms, the number of crucial points (vertices) that need to be removed to disrupt the network is always less than or equal to the number of critical connections (edges).

This makes sense as edges are the links between vertices. Therefore, you can't have a situation where disconnecting a few vertices requires fewer critical edges to be cut than those vertices represent.

Imagine a communication network where you have several call centers (vertices) and telephone lines (edges) connecting them. If cutting off calls between centers (edges) leads to total disconnection, the minimum number of such calls must logically cover more or at least equal the number of centers that could be deactivated to break connections. The limitations in connectivity stem from both locations and their ties.

--