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?