↩ back to Minimum Spanning Trees
The site's seventh Minimum Spanning Trees entry asks a different question from the other seven: not "build the minimum spanning tree" but "here's a tree someone handed me — is it actually one?" That sounds like it should require rebuilding the answer with Kruskal's or Prim's algorithm and comparing totals, but there's a cheaper route that never runs either: the cycle property. A spanning tree is minimum if and only if, for every edge left out of it, that edge is at least as expensive as the priciest tree edge on the path its two endpoints already share — because if it were cheaper, swapping it in and dropping that priciest path edge would produce a strictly cheaper spanning tree, contradicting minimality. Checking every leftover edge once is enough; no rebuild required.
The same seven-waypoint trail network every other Minimum Spanning Trees page uses — same nodes, same ten costs. Click a candidate tree below: the demo walks every leftover trail, finds the priciest trail on the candidate's own path between that leftover trail's two endpoints, and checks whether the leftover trail is at least that expensive.
Take any spanning tree T and any edge e = (u, v) not in it. Adding e to T closes exactly one cycle: e itself plus the unique tree path between u and v. If e's weight is strictly less than the most expensive edge on that path, removing that priciest path edge and keeping e instead produces a new spanning tree that costs strictly less than T — so T wasn't minimum. Run that same check for every leftover edge; if none of them can improve on their own path's maximum, no single swap can make T cheaper, and a standard fact about spanning trees — any non-minimum tree is reachable from a minimum one by a sequence of single-edge swaps that never increases cost along the way — means no sequence of swaps can improve it either. One pass over the leftover edges is a complete answer, not a heuristic.
The comparison has to allow ties: if a leftover edge costs exactly the priciest path edge, swapping doesn't change the total, and both trees are equally minimum — a genuine tie, not a defect in either one. The site's Kruskal's Reconstruction Tree answers a related question with the identical query — the priciest edge on a tree path between two nodes — just phrased as a minimum-bottleneck-path lookup instead of a pass/fail check; both rest on the same cycle property.
No sort, no Union-Find pass — the candidate tree is taken as given, and only needs a structural check (is it actually a tree at all?) before the cycle-property walk:
function isSpanningTree(numNodes, treeEdges) {
// Exactly numNodes-1 edges plus full connectivity guarantees no cycle:
// a connected graph with V-1 edges is always a tree.
if (treeEdges.length !== numNodes - 1) return false;
const parent = Array.from({ length: numNodes }, (_, i) => i);
function find(x) { while (parent[x] !== x) x = parent[x] = parent[parent[x]]; return x; }
for (const e of treeEdges) parent[find(e.a)] = find(e.b);
const root = find(0);
for (let i = 0; i < numNodes; i++) if (find(i) !== root) return false;
return true;
}
function treePath(treeAdj, u, v) {
// identical to Second-Best Spanning Tree's own treePath: a tree has exactly one path.
const parent = new Array(treeAdj.length).fill(null);
const visited = new Array(treeAdj.length).fill(false);
const queue = [u];
visited[u] = true;
while (queue.length) {
const cur = queue.shift();
if (cur === v) break;
for (const { to, edge } of treeAdj[cur]) {
if (!visited[to]) { visited[to] = true; parent[to] = { node: cur, edge }; queue.push(to); }
}
}
const path = [];
for (let cur = v; cur !== u; cur = parent[cur].node) path.push(parent[cur].edge);
return path;
}
function verifyMST(numNodes, allEdges, treeEdges) {
if (!isSpanningTree(numNodes, treeEdges)) return { valid: false, reason: 'not-a-spanning-tree' };
const inTree = new Set(treeEdges);
const treeAdj = Array.from({ length: numNodes }, () => []);
for (const e of treeEdges) {
treeAdj[e.a].push({ to: e.b, edge: e });
treeAdj[e.b].push({ to: e.a, edge: e });
}
for (const e of allEdges) {
if (inTree.has(e)) continue;
const path = treePath(treeAdj, e.a, e.b);
const maxEdge = path.reduce((m, pe) => (pe.w > m.w ? pe : m), path[0]);
if (e.w < maxEdge.w) return { valid: false, reason: 'improvable', add: e, remove: maxEdge };
}
return { valid: true };
}Skipping the structural check first means "tree path" isn't even well-defined.
A set of edges that has a cycle, or leaves a node unreached, isn't a spanning tree at all — but
treePath's breadth-first walk doesn't know that, and will happily return whatever partial
or coincidentally-connected path it finds instead of raising an error. Feed it this page's own
Candidate C (a cycle among five waypoints plus a disconnected pair) with the structural check removed:
the walk from any of the five cyclic waypoints to another one still terminates and returns a path,
built from whichever redundant cycle edge the breadth-first search happened to explore first — a
plausible-looking answer for a question that shouldn't have one. Verified against the real shipped
script: with the isSpanningTree guard disabled, Candidate C's own broken run reports
"valid" instead of catching that the edge set was never a spanning tree in the first place. The guard
above exists specifically to catch this before the cycle-property walk ever starts, and the count check
alone isn't enough on its own — six edges among seven waypoints could still be six edges clustered
around a five-node cycle with two waypoints unreached, exactly this page's own Candidate C; the
connectivity scan afterward is what actually rules that case out.
Using a strict "less than" comparison instead of allowing ties silently rejects genuine
minimum spanning trees. Whenever two or more spanning trees share the true minimum weight —
this site's own network doesn't have one, but any graph with two equal-cost edges on the right cycle
does — a leftover edge can cost exactly as much as the tree edge it could replace, and
swapping produces a different but equally minimum tree. A checker using e.w <=
maxEdge.w instead of e.w < maxEdge.w flags that tie as an improvement that
doesn't exist, reporting a genuinely minimum tree as non-minimum. Checked against a purpose-built
three-node triangle with all three edges weighted 1 (any two of the three edges form a valid minimum
spanning tree, tied at weight 2): the correct checker accepts either one, the strict variant rejects
both, every time.
Time: O(V + E) for the structural check, then O(V · E)
for the naive cycle-property walk this page implements — up to E − V + 1 leftover edges,
each paying a fresh O(V) breadth-first walk across the candidate tree to find its path,
the identical cost Second-Best Spanning
Tree's own naive walk pays for the same reason. The same fix applies here too: a
Binary Lifting structure built once over the
candidate tree in O(V log V) answers any single path-max query in O(log V)
afterward, turning the total into O((V + E) log V) — worth it once E is large
enough that V repeated tree walks stop being the cheap option. Seven waypoints and ten
trails aren't, so this demo doesn't build it.
Space: O(V + E) — the candidate tree's adjacency list plus the full edge
list.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including where verification fits once a candidate tree is already in hand — see Choosing a Minimum Spanning Tree Algorithm.