__On Dijkstra's Lemma and Kruskal's Algorithm__

__Dijkstra's Lemma__ Consider an undirected graph that consists of a single cycle and in which each vertex is marked to be either an `A`-node or a `B`-node. Then the number of `AB`-edges —i.e. edges that connect an `A`-node with a `B`-node— is even.

Let, for a given finite set of vertices, for each pair the length of the edge between them be given; for simplicity's sake all edge lengths are assumed to be distinct. We now give two theorems about "the shortest tree", i.e. the spanning tree with the smallest length, where the length of a tree is defined as the sum of the lengths of its edges.

__Theorem 0__ The longest edge of a cyclic path does not belong to the shortest tree.

__Proof__ Let `e` be the longest edge of a cyclic path. We prove Theorem 0 by showing that for any spanning tree `T` that contains `e` we can construct a shorter spanning tree. Remove edge `e` from tree `T` , which thus falls apart into two subtrees which we call `A` and `B` respectively; `e` being an `AB`-edge in the cyclic path, Dijkstra's Lemma tells us that the cyclic path contains another `AB`-edge, which we use to reconnect `A` and `B` . The resulting tree is shorter than `T` because `e` is the longest edge of the cyclic path. (End of Proof.)

__Theorem 1__ Partition the vertices into `A`-nodes and `B`-nodes. Then the shortest `AB`-edge belongs to the shortest tree.

__Proof__ Let, for a given partitioning, `e` be the shortest `AB`-edge. We prove Theorem 1 by showing that for any spanning tree `T` that does not contain `e` , we can construct a shorter spanning tree. Add edge `e` to tree `T` , thus creating 1 cyclic path, which contains `e` ; `e` being an `AB`-edge, Dijkstra's Lemma tells us that that cyclic path contains another `AB`-edge, which we remove. The resulting tree is shorter because `e` is the shortest `AB`-edge. (End of Proof.)

Kruskal's Algorithm constructs the shortest tree by processing —i.e. "rejecting" or "accepting"— the edges in the order of increasing length. At any stage, the accepted edges construct a forest —to begin with as many isolated roots as there are vertices, and finally 1 big tree of accepted edges— . Kruskal's Algorithm rejects a next edge if it forms a cycle with (some of) the edges that have already been accepted, otherwise it accepts it. In terms of the forest: the next edge is rejected if it connects two nodes from the same tree, and accepted if it connects two trees. Rejection is justified by Theorem 0, applied to the cyclic path formed in the tree; acception is justified by Theorem 1 if we partition the forest into `A`-trees and `B`-trees such that the edge under consideration is an `AB`-edge.

Austin, 3 May 1998

prof.dr. Edsger W. Dijkstra

Department of Computer Sciences

The University of Texas at Austin

Austin, TX 78712-1188

USA

Transcribed by Jennifer Lu Greene.

Last revised