28.1.5. Edge Connectivity of a Graph

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.

An edge cut is defined as a set of edges in a graph whose removal results in the graph becoming disconnected. In simpler terms, if you have a graph made up of points (vertices) connected by lines (edges), an edge cut involves taking away certain lines so that some points no longer connect with others. The condition of disconnection is crucial; removing edges should separate parts of the graph into distinct components.

Think of a city map where intersections represent points (vertices) and roads represent lines (edges). If you remove specific roads, parts of the city can no longer be reached from others. For example, if you cut off the main highway that connects two neighborhoods, the neighborhoods become separate.

So, again similar to the question that we asked for the vertex cut, let us answer this question whether every connected graph which has nodes as an edge cut or not. Again, the answer is yes, except for the case when your graph is already a graph with just a single node and no edges.

This statement discusses that in any connected graph, it's always possible to find a set of edges whose removal will disconnect the graph, with one exception: if the graph consists solely of one node without any edges. In all other cases, by removing the right set of edges (the edge cut), one can ensure that the graph separates into multiple parts.

Imagine a network of computers; if every computer is connected to multiple others, removing a few connections (edges) can isolate parts of the network, preventing some computers from communicating with others. However, if there's only one computer and no connections, you can't remove anything since there's nothing to cut off.

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.

The edge connectivity (denoted as λ) of a graph is quantified by the smallest number of edges that must be removed to disconnect the graph. It's a measurement of how tightly interconnected the vertices are—lower edge connectivity indicates that the graph could easily become disconnected with the removal of fewer edges.

Consider a network of highways connecting several cities. The edge connectivity can be likened to the crucial highways; if a few important roads are removed, it may be impossible to travel between certain cities. If there are many alternative routes, the edge connectivity is high.

If your graph was a bridge or cut edge then λ will be 1. But if your graph does not have a bridge then you need to delete more than one edge to delete the graph to disconnect it.

This definition highlights special cases based on the structure of the graph. A bridge (or cut edge) is an edge which, if removed, increases the number of disconnected components. If the graph has at least one bridge, the edge connectivity is 1, indicating that only one edge removal suffices to disconnect the graph. If there are no bridges, more edges will be required to achieve disconnection.

Think of bridges in a physical network of roads, where each bridge represents an edge. If a town's only bridge gets destroyed (the bridge being the edge), it can become isolated, showing edge connectivity of 1. But if all roads lead in and out of town, and there is no single bridge, you might need to close several roads to isolate the town.

To take care of the special case, I modify my definition and my modified definition of edge connectivity is the following. I define edge connectivity to be the minimum number of edges which needs to be deleted to either disconnect the graph or produce a graph with a single node.

This modified definition of edge connectivity considers both condition of disconnection and creating a single-node graph. The addition accounts for cases where the graph may already consist of a single node (no edges), making the original definition unapplicable. Thus, the new definition ensures that edge connectivity remains meaningful across all types of graphs.

Imagine a situation in a classroom where if all connections (lines) between students (nodes) are removed, we can produce a solitary student. In this case, even though several students might leave the class, the removal of just a few can lead to scenarios where the remaining connections are minimal or even non-existent.

It is easy to verify that your edge connectivity will be in the range 0 to n - 1, where n is the number of nodes in your graph. If your graph is already disconnected, then you do not need to delete any edge to disconnect it. But if your graph is a complete graph, then you just delete n - 1 edges incident with any node then that node gets disconnected from the rest of the network.

The edge connectivity of a graph is bound between 0 and n - 1 (where n represents the number of nodes). If the graph is already disconnected, the edge connectivity is 0, as no edges need to be removed. Conversely, in complete graphs, the maximum edge connectivity is n - 1, as one could remove all but one edge incident to any node to ensure that singular node is disjointed from all others.

In a complete network of friends (where everyone knows everyone), you can visualize edge connectivity. If you only know one friend (node), disconnecting them (removing an edge) leaves you alone, which signifies maximal connectivity until that point. In this case, there's no such thing as further disconnection since all other ties remain.

--