3.4. Minimum Separator Lemma

Let us assume that we have this weighted undirected graph and we look at the set of vertices v, right and we assume that it is divided into two paths, right. So, this is called partitioning. So, there are two separate disjoint paths which I will call u and w, and I am assuming that both of these are non-empty. So, there is at least one vertex u and one vertex w. Now, let me look at the smallest edge which goes across this partition. Remember that the whole graph is connected. So, they must be a way to go from u to w. Some of all the ways I can go from u to w. Let me check the smallest edge. Let me call the end point small u and small w. So, now, the claim is that every minimum cost spanning tree must include this edge.

In any weighted undirected graph, if you divide the vertices into two non-empty subsets (called u and w), there is at least one edge that connects these two subsets. The Minimum Separator Lemma states that the smallest edge (in terms of weight) connecting the two subsets must be part of any minimum cost spanning tree for that graph. This is because, if that edge is omitted, we would be able to create a new spanning tree with a lower cost by including it, thereby violating the premise that it was a minimum spanning tree.

Imagine you have two neighborhoods (u and w) that are separated by a river (the edge). The only bridge (the smallest edge) connecting them is very crucial. If the bridge is the cheapest way to cross, then any route that doesn't use the bridge would be longer (or more expensive), which makes the bridge necessary for ensuring everyone can get to the other side with the lowest travel cost.

So, now why is the case? So, let us assume that we have these two parts. So, I will draw one part say this yellow thing and let us call this u and which have not drawn a boundary for, this is v, and this is w. So, now let us look at the smallest edge connecting u and w, right. So, now the claim is that this must be in every minimum cost spanning tree. So, suppose it is not. So, then suppose there must be some minimum cost spanning tree, because we know that the graph is connected. So, there are many spanning trees unless assume that the minimum cost spanning tree T which does not include this edge. In that tree u must be connected to the tree, because any spanning tree connects all the vertices. So, there is a red path from u to w in my hypothetical spanning tree T which does not include this edge.

To prove the lemma, suppose the smallest edge connecting sets u and w is not included in a minimum cost spanning tree T. If T connects all vertices, there must be another path (not using the smallest edge) connecting u and w. By removing an edge from this path and adding the smallest edge, we create a new tree (T prime) that has a lower total weight. This contradicts our assumption that T was the minimum spanning tree, thus proving that the minimum edge must be included in every minimum cost spanning tree.

Think of the shortest path between two points in a city. If you find a shortcut (the smallest edge) that wasn’t on the original route, using this shortcut results in less travel time. If the original route didn't include this shortcut, then it can't truly be the fastest way to get to your destination.

Before we move ahead, I just want to make one small remark. So, we would have to be careful when we prove this lemma a little bit. So, it is true that among all the edges going from inside to outside, uv is the smallest one. So, we might be tempted to just say, so uv is the smallest one, pick any edge in my given tree T prime given tree T which goes from inside to outside, then replace. So, for instance, we might accidentally pick up this edge and replace it with this edge.

When applying the minimum separator lemma, it's crucial to select the correct edge in the existing spanning tree to replace with the smallest edge connecting the partitions. Choosing an arbitrary edge can lead to the scenario where the new tree becomes invalid or doesn't connect all vertices. We need to ensure that the edge we are replacing allows for a continuous path in the tree from inside the partition to the outside.

Consider a group of friends (a tree) where every friend is connected via specific friendships (edges). If you want to introduce a new friend (the smallest edge) to the group, you can't just replace any existing friendship. You need to ensure that the new friend can connect properly to the group without breaking any existing connections.

So, once we had this lemma, the correctness of prim's algorithm is very obvious. So, at every stage remember in Prim's algorithm, we have built this tree TV which consists of a few edges, and then we have everything just lying outside and now among these we want to connect one of that, right. So, if you think of this said the set inside is my u and the set outside is my w, and we are picking by assumption in Prim's algorithm, the smallest weight edge which connects u to w. By this minimum separator lemma, this edge must line every spanning tree.

The Minimum Separator Lemma substantiates that at each stage of Prim's algorithm, the edge chosen to connect the growing tree to the remaining vertices is indeed the smallest weight edge available. Since the lemma states that the minimum weight edge across any partition must be included in a minimum spanning tree, Prim's algorithm inherently satisfies this condition by design. Thus, the correctness of Prim's algorithm in establishing minimum spanning trees is assured.

Imagine you're building a new subway system (the tree). At every station (vertex) you choose the cheapest track (edge) to connect to the next, ensuring that you're always creating the most efficient route. The lemma guarantees that you won't miss a critical track that could save costs even if you're just considering local options.

--