Does the Minimum Spanning Tree include the TWO lowest cost edges?

Question

Wikipedia's Minimum Spanning Tree reads:

Minimum-cost edge

If the minimum cost edge e of a graph is unique, then this edge is included in any MST.

Proof: if e was not included in the MST, removing any of the (larger cost) edges in the cycle formed after adding e to the MST, would yield a spanning tree of smaller weight.

So far so good, but what about the two minimum cost edges? Since I cannot think of any counter-example for which it doesn't hold, I have written the following Python script. It generates a random graph, weights it with consecutive integers (1, 2, 3, ...), calculates its (unique) MST, and repeats until the second lightest weight of the MST is not 2.

n = 8
p = 0.3
while True:
    G = nx.erdos_renyi_graph(n, p)
    for (w, (x, y)) in enumerate(G.edges(), 1):
        G[x][y]["weight"] = w
    edges = list(nx.minimum_spanning_edges(G, data=False))
    weights = sorted(G[x][y]["weight"] for (x, y) in edges)
    # print(weights)
    if weights[1] != 2 and len(weights) > 1:
        print(weights)
        break

You can convince yourself that this script works as intended by uncommenting the first print, or by replacing weights[1] != 2 by weights[2] != 3 (which makes it stop when the MST doesn't includes the edge of weight 3).

However, it doesn't terminate, which seems to indicate that the Wikipedia's proposition could be extended to the two lowest cost edges.

There is a possibility that such graphs are rare, that the parameters of my random generator are biased against them, or my consecutive weights are wrong somehow.

What do you think? Can you prove this extension, or produce a counter-example?

Answer 1

If the MST does not contain at least one among the two minimum-cost edge then add it to the MST (you get a graph with a single loop and the loop has length 3 or larger) remove from the loop the edge having larger cost (it costs more than the one you just introduced) and you are left with a Tree and this tree is Spanning and it costs less than the original one.

Proved by contradiction!

Answer 2

For simple graphs*, it is true for the following reason:

1. Kruskal’s algorithm is correct
2. Kruskal’s algorithm works as follows:
   • sort the edges by increasing weight
   • repeat: pop the cheapest edge, if it does not create cycles, include it in the MST
3. Two edges cannot construct a cycle in a simple graph

By the correctness of Kruskal’s algorithm, the two uniquely smallest weight edges are always part of an MST. (It also follows that the three uniquely smallest weight edges are always part of an MST unless those three form a triangle.)

* Simple graphs have no parallel edges

Answer 3

Assuming that the graph has at least $3$ vertices, is connected, and edges have distinct weights you can see that the two edges with the lowest weights must belong to the (unique) MST of the graph by noticing that they cannot induce any cycle and hence they must be selected by Kruskal's algorithm.

Alternatively, you can notice that each cycle must contain at least $3$ edges and hence none of the two edges with the smallest weights can be the edge of maximum weight in the cycle.