From a Weighted Edge List to a Tree
A connected graph can have many spanning trees, and their total edge weights need not be equal. Kruskal’s algorithm builds a spanning tree by considering edges from lightest to heaviest and accepting an edge only when it joins two currently separate components. The rule is simple to apply, but it requires careful bookkeeping: “separate” refers to the components formed by the edges already accepted, not just to whether the two endpoints were adjacent in the original graph.
Throughout, graphs are finite and simple. A weighted graph assigns a real number, called the weight, to each edge. A spanning tree is a subgraph containing every vertex that is connected and has no cycle. Its total weight is the sum of the weights of its edges. A minimum spanning tree is a spanning tree of least total weight among all spanning trees of the graph. The input to the algorithm here is a connected weighted graph with at least one vertex.
When several edges have the same weight, their relative order may be chosen arbitrarily, but it should be specified when tracing an example. The algorithm’s cycle test is independent of the weights: an edge whose endpoints are already connected by accepted edges is rejected because adding it would create a cycle.
The Procedure and Its Invariant
Start with no accepted edges. Each vertex is its own component.
Arrange all edges by nondecreasing weight. Choose and record an order among tied edges if needed.
For each edge \(uv\), accept it if \(u\) and \(v\) are in different current components. Otherwise reject it. After acceptance, merge those two components.
As soon as \(n-1\) edges have been accepted, return the accepted edges and their total weight.
The basic invariant is that the accepted edges form a forest: a graph with no cycles, not necessarily connected. Initially the accepted-edge graph has no edges, so it has no cycles. If an edge joins different components, adding it cannot create a cycle, because a cycle using that edge would require a path between its endpoints before it was added. If an edge joins vertices in the same component, there is already a path between them; adding the edge closes a cycle. This proves both the invariant and the stated cycle test.
Proof. The invariant just established shows that the accepted edges always form a forest. If the algorithm stops after accepting \(n-1\) edges, this forest is connected: a forest on \(n\) vertices with \(c\) components has \(n-c\) edges, so \(n-1\) edges imply \(c=1\). For completeness, the forest edge count follows by applying the tree edge count \(q-1\) to each component of order \(q\) and summing over the \(c\) components: the total is \(n-c\).
It remains to see that the scan reaches \(n-1\) accepted edges when \(n>1\). If the accepted forest has more than one component, connectedness of the original graph guarantees an original edge between two of those components: take a path in the original graph from a vertex in one component to a vertex in another, and use the first edge on that path that leaves the first component. When that edge is scanned, either its endpoints are still in different current components and it is accepted, or earlier accepted edges have already joined them. Thus, while more than one component remains, scanning all edges cannot finish without reducing the number of components. Each accepted edge reduces that number by one. Starting at \(n\) components, exactly \(n-1\) acceptances produce one component. The accepted graph is therefore connected and acyclic, hence a spanning tree. When \(n=1\), there are no edges to accept and the single vertex is connected to itself by the length-zero path; it is acyclic. \(\square\)
This proposition establishes that the procedure constructs a spanning tree. The nondecreasing weight order is what makes it a minimum-spanning-tree method; the exchange argument using the cut property explains that optimization claim. The examples below focus on carrying out and checking the edge scan.
Tracing the Scan
Worked Example: A Rejected Edge Before the Stop
Let \(G\) have \(V=\{1,2,3,4\}\) and weighted edge list \(12:1,\ 23:2,\ 13:3,\ 34:4,\ 24:5\), where the number after the colon is the edge weight. The graph is connected: for example, \(1,2,3,4\) is a path. The sorted order is \(12,23,13,34,24\).
Track the components of the accepted-edge graph. The notation \(\{12\}\) means that vertices \(1\) and \(2\) are in one component; any ungrouped vertex is a singleton component.
| Edge scanned | Decision | Components after the decision |
|---|---|---|
| \(12\), weight \(1\) | Accept | \(\{1,2\},\{3\},\{4\}\) |
| \(23\), weight \(2\) | Accept | \(\{1,2,3\},\{4\}\) |
| \(13\), weight \(3\) | Reject: \(1\) and \(3\) are already connected by \(1,2,3\) | \(\{1,2,3\},\{4\}\) |
| \(34\), weight \(4\) | Accept | \(\{1,2,3,4\}\) |
There are \(n=4\) vertices, so the stopping count is \(n-1=4-1=3\). The three accepted edges are \(12,23,34\), with total weight \(1+2+4=7\). The edge \(24\), of weight \(5\), is not scanned: the stopping rule applies as soon as the third edge is accepted.
Check: the accepted edges form the path \(1,2,3,4\), so they connect all four vertices and contain no cycle. They number \(3=4-1\), as required for a spanning tree. Re-adding their weights gives \(1+2+4=7\).
Worked Example: Tied Weights and a Cycle Test
Let \(G\) have \(V=\{1,2,3,4,5\}\) and weighted edge list \(12:1,\ 23:2,\ 34:2,\ 14:2,\ 45:3,\ 25:3,\ 13:4\). This graph is connected, since \(12,23,34,45\) form a path through all five vertices. To make the tie handling explicit, scan the weight-\(2\) edges in the order \(23,34,14\), and the weight-\(3\) edges in the order \(45,25\). The full scan order would be \(12,23,34,14,45,25,13\).
| Edge scanned | Decision | Components after the decision |
|---|---|---|
| \(12\), weight \(1\) | Accept | \(\{1,2\},\{3\},\{4\},\{5\}\) |
| \(23\), weight \(2\) | Accept | \(\{1,2,3\},\{4\},\{5\}\) |
| \(34\), weight \(2\) | Accept | \(\{1,2,3,4\},\{5\}\) |
| \(14\), weight \(2\) | Reject: \(1\) and \(4\) are already connected | \(\{1,2,3,4\},\{5\}\) |
| \(45\), weight \(3\) | Accept | \(\{1,2,3,4,5\}\) |
The rejected edge \(14\) would close the cycle \(1,2,3,4,1\), using the already accepted edges \(12,23,34\). Since \(n=5\), the stopping count is \(5-1=4\). The accepted edges are \(12,23,34,45\), and their total weight is \(1+2+2+3=8\). The edges \(25\) and \(13\) are not reached after the stopping count is met.
Check: the accepted edges form the path \(1,2,3,4,5\); hence they connect all vertices and have no cycle. Their number is \(4=5-1\), and adding their weights again gives \(1+2+2+3=8\). Ties do not mean that every edge of that weight must be accepted: \(14\) is rejected because its endpoints are already connected.
Worked Example: Merging Separate Components
Let \(G\) have \(V=\{1,2,3,4,5,6\}\) and weighted edge list \(12:1,\ 34:1,\ 23:2,\ 13:2,\ 45:2,\ 56:3,\ 46:3,\ 25:4,\ 16:5\). The graph is connected, since the listed edges include the path \(1,2,3,4,5,6\). Choose the scan order \(12,34,23,13,45,56,46,25,16\), which respects nondecreasing weights and specifies the tie order.
| Edge scanned | Decision | Components after the decision |
|---|---|---|
| \(12\), weight \(1\) | Accept | \(\{1,2\},\{3\},\{4\},\{5\},\{6\}\) |
| \(34\), weight \(1\) | Accept | \(\{1,2\},\{3,4\},\{5\},\{6\}\) |
| \(23\), weight \(2\) | Accept | \(\{1,2,3,4\},\{5\},\{6\}\) |
| \(13\), weight \(2\) | Reject: \(1\) and \(3\) are already connected | \(\{1,2,3,4\},\{5\},\{6\}\) |
| \(45\), weight \(2\) | Accept | \(\{1,2,3,4,5\},\{6\}\) |
| \(56\), weight \(3\) | Accept | \(\{1,2,3,4,5,6\}\) |
The first two accepted edges create two separate two-vertex components. Edge \(23\) joins them, so the accepted edges now connect vertices \(1,2,3,4\). Edge \(13\) would close the cycle \(1,2,3,1\), so it is rejected. Edges \(45\) and \(56\) then join the remaining vertices. Since \(n=6\), the algorithm stops after \(6-1=5\) acceptances. Their total weight is \(1+1+2+2+3=9\).
Check: the accepted edges are \(12,34,23,45,56\). They connect all six vertices: the resulting path can be written \(1,2,3,4,5,6\). They have \(5=6-1\) edges and no cycle. Their weights sum to \(1+1+2+2+3=9\).
Common Mistakes and Practical Checks
Confusing original adjacency with current connectivity. An edge is rejected not because it was already present in the original graph, but because its endpoints have become connected through accepted edges. In the first example, \(13\) was an original edge, but it was rejected only after \(12\) and \(23\) had been accepted.
Accepting every light edge. In the tied-weight example, a mistaken scan might accept \(14\) because its weight is \(2\). That would be wrong: after accepting \(12,23,34\), the vertices \(1\) and \(4\) are already joined by the path \(1,2,3,4\). Accepting \(14\) would create a cycle. Weight order determines which edge is considered; the component test determines whether it is accepted.
Stopping at the wrong time. The stopping count is \(n-1\) accepted edges, not \(n-1\) scanned edges. Rejected edges do not count toward it. Once the stopping count is reached, later edges need not be examined to construct the spanning tree.
For a hand calculation, keep three checks visible: record the sorted edge order, update the component groups after every accepted edge, and count accepted edges separately from scanned edges. At the end, confirm that all vertices lie in one component, that no accepted edge was added within a component, and that the accepted-edge count is \(n-1\). These checks verify the tree construction and its stated total weight. The minimum-weight claim concerns comparison with every other spanning tree; the cut property and an exchange argument explain why the nondecreasing scan achieves that objective.
Check Your Understanding
For each question, state the graph or scan information needed to support your answer.
- In a connected graph on \(7\) vertices, how many edges must Kruskal’s algorithm accept before it stops?
- Suppose an edge \(uv\) is being scanned and the accepted edges already contain a \(u\)-\(v\) path. What happens if \(uv\) is accepted, and what does the algorithm do instead?
- Let \(V=\{a,b,c\}\) and let the weighted edges be \(ab:1,\ bc:1,\ ac:2\). Give one valid scan order, record each decision, and find the total weight of the returned tree.
- Why can two edges of equal weight be scanned in either order, and what information must still be checked for each one?
- Explain why a forest with \(n-1\) edges on \(n\) vertices is connected, and how this fact helps check Kruskal’s output.