6
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ "it doesn't terminate" You mean it hasn't terminated yet after running it for a few minutes, which is no proof that it will never terminate. $\endgroup$ Nov 19, 2021 at 16:23

3 Answers 3

3
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ But, as the other answer mentions, this requires that the graph is simple: that there are no parallel edges. If that doesn't apply, it's easy to see that two edges can create a loop, and if the two lowest-cost ones do, only one will be included in the MST. $\endgroup$
    – ilkkachu
    Nov 20, 2021 at 16:56
23
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks, it's quite convincing. Nevertheless, I am afraid that invoking a whole algorithm is a bit overkill. For instance, in the Wikipedia page, the theoretical results are presented before the algorithms. I will think of a more economic proof. $\endgroup$
    – Aristide
    Nov 19, 2021 at 9:26
  • 6
    $\begingroup$ You can prove the correctness of Kruskal's by induction (it's rather simple), and then your observation will follow immediately from that proof. But I assure you that it is normal procedure to use the correctness of algorithms to prove structural properties. $\endgroup$
    – Pål GD
    Nov 19, 2021 at 9:37
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I noticed :D Too bad it was not simultaneous! $\endgroup$
    – Steven
    Nov 18, 2021 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.