Minimum edge in a set of edges which connects a graph

Question

The following is an example from my graph theory and algorithm course:

Let A be a minimal subset of edges of a weighted undirected graph G (distinct weight), such that if we remove A from G then G becomes disconnected. The lightest edge in A must be in any MST.

Why this is a correct fact? I couldn't understand it.

Answer 1

Here's how I think of it. It's given that A is a set of edges that when removed disconnects G. We could say that A connects (at least) two subsets of nodes in G, G1 and G2. There can be no edges linking G1 and G2 that don't go through A, because otherwise the connection of G1 and G2 would not depend on A. Also denote m as the minimum edge within A (not necessarily the minimum of G, although it could be!).

So the question is, can you make the minimum path from G1 to G2 through A without taking its minimum edge m? Well think of another subgraph which is all of the nodes which contain an edge within A. So at least one node from G1 and one node from G2 (such that they are connected through A). The MST of this subgraph must include m, because a MST must include the smallest edge weight. And the MST of G must include the MST of A, else we would be getting from G1 to G2 in a suboptimal way.

Answer 2

According to the definition of minimal edge cut:

A minimal edge cut is an edge cut such that if any edge is put back in the graph, the graph will be reconnected.

In the following figure:

The set, A = {a, b, c, d} is a minimal edge cut.

If A is removed from G, the graph becomes disconnected.

Now, the property: "lightest edge in A must be in any MST" can be explained by the Cut Property:

Therefore the statement is true, because,

The lightest edge of the set A = e = min(a, min(b, min(c,d))) will be the part of MST.