28.1. Discrete Mathematics

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 defined as a subset of vertices in a graph such that when those vertices are removed, the graph becomes disconnected. This means that the remaining vertices are not all reachable from one another. An articulation point in a graph is a special case of a vertex cut where the removal of that single point causes disconnection. Sometimes, more than one vertex may be necessary to achieve disconnection, especially if no single vertex causes disconnection.

Consider a city represented as a graph where intersections are vertices and roads are edges. If a specific intersection is removed, it could disconnect parts of the city, much like how removing an articulation point disconnects the graph.

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 is denoted by κ(G) and represents the minimum number of vertices required to disconnect the graph. For example, if a graph has a vertex connectivity of 2, it means we need to remove at least 2 vertices to cause disconnection. If a graph contains an articulation point, its vertex connectivity is at least 1. If the graph is already disconnected, the vertex connectivity is 0.

Imagine a network of computers connected to each other. The vertex connectivity indicates how many computers you would need to take offline to isolate parts of the network. If you only need to take down 2 computers to create isolation, the network's vertex connectivity is 2.

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.

An edge cut is a set of edges whose removal results in a disconnection of the graph. If we share the same definition as with vertex cuts, we are not focusing on the minimum size but merely checking whether a given set of edges is sufficient to disconnect the graph.

Think of a water supply network represented by a graph where pipes are edges. If certain pipes (edges) are removed, parts of the network become isolated, reducing access to water in those segments.

So now let us 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 by λ, measures the minimum number of edges required to be removed to disconnect the graph. For example, if λ is 2, it indicates that two edges must be cut to cause disconnection in the network.

In a train network, if two critical tracks (edges) are removed, certain stations can become inaccessible. The edge connectivity would be the minimum number of tracks necessary to cut to ensure at least one station is isolated.

So, now we want to fix some upper bounds on the vertex connectivity and edge connectivity. So, let us first prove an upper bound on the vertex connectivity.

For a connected, non-complete graph, the vertex connectivity is always less than or equal to the minimum degree of the graph. This essentially means that the least connected vertex dictates how many vertices you can remove before disconnection occurs. Similarly, edge connectivity follows the same principle.

If a building has several rooms with doors (edges) connecting them, the room with the least number of doors suggests the maximum number of rooms that can be isolated at once. If one room lets out to multiple others, its disconnection won't lead to disconnection of all rooms.

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.

The theorem states that in a connected and non-complete graph, the vertex connectivity will always be less than or equal to the edge connectivity. This indicates that if you understand how many edges need to be removed to disconnect the graph, you also have an insight into how many vertices need to be removed to achieve disconnection.

Imagine a friendship network where friends (vertices) are connected by relationships (edges). If cutting relationships between friends results in isolation, the number of friendships lost reflects the potential number of friends that would need to be removed to create isolation.

--