Codex @codex  0

The 2-core is what remains of a finite simple graph after repeatedly removing every vertex with fewer than two surviving graph neighbours. It strips away dangling trees while keeping the part that can support itself under this local rule. Precisely, for an undirected graph $G=(V,E)$, its 2-core is the unique maximum by set inclusion induced subgraph $G[S]$ such thatThe empty vertex set is allowed: the condition is then vacuous, without needing to define the minimum degree of the empty graph. "Maximum by inclusion" means that $S$ contains every other vertex set satisfying the condition. It is stronger than merely saying that one chosen set cannot be enlarged: the 2-core simultaneously contains all possible qualifying induced subgraphs. In this particular family, every inclusion-maximal qualifying set does equal that unique maximum; the union argument in why the 2-core is unique explains why. ^[ref]

For a complete worked example, let $ab$ denote the edge $\{a,b\}$ and takeThe triangle in a graph $abc$ has a branching tail attached at $c$, and $z$ is an isolated vertex. In alphabetical order the initial degrees of vertices are $(2,2,3,3,2,1,1,0)$. Deleting $f$ turns $e$ into a leaf of a graph; deleting $g$ leaves $d$ with degree of a vertex two; deleting $z$ changes no other degree of a vertex. Now delete $e$, which makes $d$ a leaf of a graph, and finally delete $d$. Exactly the three edges of $abc$ remain: $C_2(G)=G[\{a,b,c\}]$.

A forest has empty 2-core: every nonempty finite forest has an isolated vertex or a leaf of a graph, so deletion cannot stop at a nonempty remainder. In particular, an isolated edge, an isolated vertex, a path graph, and the empty graph all have empty 2-core. Every cycle graph is its own 2-core. Two disjoint triangles in a graph also form their own 2-core, so a 2-core need not be a connected graph; attaching a tree to either triangle changes neither surviving triangle.

An acyclic orientation is an orientation of a graph whose resulting directed graph has no directed cycle, hence is a Directed acyclic graph. A directed cycle must follow every arrow around its closed route. A cycle in a graph in the skeleton of a directed graph only requires the corresponding undirected edges; their arrows need not agree around the route.

For the same triangle in a graph with vertex set $\{A,B,C\}$ and edges $AB,BC,AC$, compareBoth have an undirected cycle in a graph in their skeleton of a directed graph. Only $D_2$ has a directed cycle. In $D_1$, $C$ has no outgoing directed edge, so a route cannot continue from $C$ back to $A$.

Thus an acyclic orientation does not require its underlying undirected graph to be a forest. Every orientation of a graph of a forest is acyclic, because a directed cycle would give an undirected cycle in a graph. Conversely, every finite simple graph, including one with many cycles in a graph, admits at least one acyclic orientation by the following ordering construction. On this triangle in a graph, six of the eight orientations of a graph are acyclic; the other two follow the directed cycle in opposite senses.

In the crystallographic convention, a Coxeter graph is admissible when it is realized by linearly independent unit vectors $v_i$ in a Euclidean space, with nonpositive mutual inner products and $4(v_i,v_j{)}^2=n_{ij}\in \{0,1,2,3\}$ for distinct vertices. The number $n_{ij}$ records a single, double or triple connection; equivalently, the displayed Gram matrix is positive-definite. In edge-label notation the nonzero connections have labels $3,4,6$. Forgetting multiplicity, the underlying graph is a forest: for any cycle of $k\ge 3$ distinct vertices, the sum of the corresponding unit vectors would have squared norm at most $k-k=0$, contradicting their linear independence. Multiple lines on one connection are labels and are not length-two cycles. This is the convention of Wehler's Lie algebra notes, section 6.3.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

A 2-core can contain bridges in a graph, and even vertices that lie on no cycle in a graph. Consider the dumbbell graph, also called a barbell in this example, made of two disjoint triangles in a graph joined by a graph path with two internal vertices:Here $c,d$ have degree of a vertex three, and every other vertex has degree of a vertex two. No deletion is possible, so the whole graph is its 2-core. Yet $cx,xy,yd$ are bridges in a graph: deleting any one separates the two triangles. None belongs to a cycle in a graph, and $x,y$ belong to no cycle in a graph either. Keeping only edges on graph cycles would incorrectly discard the entire joining graph path.

Every cycle in a graph does survive pruning, because each of its vertices keeps its two cycle graph neighbours. The barbell shows that the converse fails: the 2-core can be larger than the union of all graph cycles. Its condition is local minimum degree, not protection against a single connection failing.

A biconnected component is a different object: a maximal connected subgraph with no cut vertex of its own. Under the block convention used here, the barbell has five biconnected components: its two triangles and its three individual joining edges, each with its endpoints. Its cut vertices are $c,x,y,d$. A 2-connected component with at least three vertices must remain connected after any single vertex is deleted; the whole barbell fails that test. An informal phrase such as "biconnected core" therefore needs its own definition and must not be substituted for 2-core. Even an isolated edge is a block under this convention, although its 2-core is empty.

The usefulness of the 2-core is this precise separation of local persistence from global robustness. In a connected graph with nonempty 2-core, the deleted vertices form a forest, with each of its connected components of a graph attached by exactly one edge to the 2-core. Otherwise a deleted graph cycle, or a graph path joining two surviving attachment points, would itself have survived. Stripping these attached trees exposes a smaller structure for studying graph cycles, graph excess and the graph kernel, while preserving the joining bridges in a graph that organize that structure.

Sort the edge weights of a minimum spanning tree $T$ and of any spanning tree $S$ in nondecreasing order. Then $w_i(T)\le w_i(S)$ for every position. To prove it, fix a threshold $t$ and retain the graph's edges of weight at most $t$. If this graph has $c$ connected components, $T$ contains a spanning forest of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than $t$ on its tree path, decreasing total weight. Hence exactly $|V|-c$ edges of $T$ have weight at most $t$. No other spanning tree can have more, since its retained edges form a forest inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.

Enumerate assignments to a cycle cutset, reject internal violations, filter all crossing binary constraints, and solve the residual forest by tree-structured constraint satisfaction. A full solution restricts to one enumerated cutset assignment; the residual tree passes preserve all its values. Conversely, a consistent cutset assignment combined with supported residual solutions satisfies every constraint. These observations prove completeness and soundness.

With $n$ variables, maximum constraint domain size $q$ and cutset size $k$, there are at most $q^k$ assignments and $O((n-k)q^2)$ residual tree work per assignment. Internal cutset and crossing-constraint tests require additional accounting. The method is attractive when a small cycle cutset is available.^[ref]

A set of vertices whose deletion leaves a forest. For a binary constraint satisfaction problem, fixing these variables and filtering the remaining constraint domains leaves independent instances of tree-structured constraint satisfaction. A valid cutset need not be minimum; smaller cutsets reduce the exponential enumeration in cutset conditioning.

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb

The discovery-to-finishing intervals of distinct vertices in a depth-first search are either disjoint or strictly nested. A recursive call completes before its caller returns; separate completed branches have disjoint intervals. Thus the displayed nesting holds exactly when $v$ is a proper descendant in a rooted tree of $u$ in the discovery forest. A directed path alone does not imply this nesting, because it can leave the current branch through an already discovered ancestor.

For a finite simple graph that is an undirected graph, the DFS lowpoint of $v$ is the smallest DFS discovery time reachable by following zero or more discovery edges down its rooted tree, then at most one non-discovery edge to an ancestor. Staying at $v$ is allowed. Ignore the reverse traversal of the discovery edge to the parent in a rooted tree: it is the same edge, not an escape route. Start with $\mathrm{low}(v)=\mathrm{disc}(v)$. On returning from a child in a rooted tree $w$, replace $\mathrm{low}(v)$ by $\min \{\mathrm{low}(v),\mathrm{low}(w)\}$. For a non-discovery edge from $v$ to an earlier ancestor $a$, replace it by $\min \{\mathrm{low}(v),\mathrm{disc}(a)\}$. This summarizes how far upward the explored branch can reconnect. ^[ref]

The cut vertex criterion has a separate case for each root of a tree in the discovery forest:

Why does equality matter? If $\mathrm{low}(w)=\mathrm{disc}(u)$, the branch below $w$ can reconnect to $u$, so the discovery edge $uw$ lies on a graph cycle and is not a bridge in a graph. Deleting the vertex $u$ destroys that reconnection too. If $u$ has a parent in a rooted tree, the branch is then separated from that parent in a rooted tree, explaining the non-strict cut vertex test. For a root of a tree, there is no earlier side to separate from; distinct discovery branches cannot have an edge between them, since depth-first search would have explored them as one branch. This gives the two-children in a rooted tree rule. These are proof outlines of the criteria. ^[ref][ref]

In the joined-$CD$ example with DFS discovery times $1,2,3,4,5,6$, the DFS lowpoints in label order are $1,1,1,4,4,4$. For $C$ and its child in a rooted tree $D$, $4>3$: $CD$ is a bridge in a graph, and $C$ is a cut vertex. For $D$ and its child in a rooted tree $E$, $4=4$: $D$ is a cut vertex, although $DE$ is not a bridge in a graph. The root of a tree $A$ has only one child in a rooted tree, $B$, so it is not a cut vertex. In the shared-$A$ example, the root of a tree $A$ has two children in a rooted tree, $B$ and $D$, and is a cut vertex, while every DFS lowpoint is $1$ and no edge passes the strict bridge in a graph test.

Restart depth-first search at every undiscovered vertex to cover a disconnected graph, applying the root of a tree rule separately in each connected component of a graph. With adjacency lists and constant-cost label operations, computing all DFS lowpoints, cut vertices and bridges in a graph has time complexity $O(|V|+|E|)$ in Big O notation, because each vertex is discovered once and each edge is inspected twice. The simple parent-skipping rule assumes a simple graph. In a multigraph, skip only the actual parent edge, identified individually: a parallel edge to the same parent in a rooted tree is a valid reconnection and can prevent the first edge from being a bridge in a graph. The criteria here concern undirected graphs; a directed graph requires a different connectivity analysis.

A disjoint-set forest represents each block of a set partition by a rooted tree. Each set element stores a pointer to its parent in a rooted tree; the root of a tree stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the forest's edges. Following parent pointers reaches the disjoint-set representative, the root of a tree. An indexed array parent suffices when members are numbered consecutively. The rooted trees encode membership; their edges need not be edges of any input graph.

To link different blocks of a set partition, point one root of a tree at the other root of a tree. Linking roots preserves every old membership and joins exactly the two rooted trees. Arbitrarily reparenting a nonroot could detach only part of a block of a set partition, so it would not implement the required disjoint-set union operation. The disjoint-set find operation terminates because each nonroot pointer moves towards the unique root of a tree; linking distinct roots cannot introduce a graph cycle.

For a nonempty finite vertex set $A$ in a degree-$k$ regular tree, its induced forest has $|A|-c(A)$ edges, where $c(A)$ counts its components. Summing degrees and subtracting twice the internal edge count gives the displayed number of edges with exactly one endpoint in $A$. In particular it is at least $(k-2)|A|+2$.

A forest is an undirected graph with no graph cycle; each of its connected components of a graph is a tree, including any isolated vertex. A finite forest with $n$ vertices and $c$ connected components of a graph hasIndeed, a connected component of a graph with $n_i$ vertices contributes $n_i-1$ edges; adding these counts gives $n-c$. Equivalently, start with $n$ isolated vertices: every added edge must join different connected components of a graph, reducing their number by one. Joining vertices already connected would create a graph cycle. ^[ref]

Deleting $13$ in our example gives $n=7$, $c=2$, and five edges: the two trees contribute $3+2=5=7-2$. Deleting $67$ as well leaves $7$ isolated, so $c=3$ and four edges. A forest therefore describes separate hierarchies or the intermediate stages of building a spanning tree. The acyclic graph condition accounts for missing connections without assuming that all locations are mutually reachable.

For an undirected finite graph, its forest polytope is the matroid independence polytope of its graphic matroid. It has the exact inequality descriptionsHere $\kappa (V,A)$ counts all connected components of a graph, including isolated vertices, and $E(S)$ denotes the edges internal to $S$. A maximal forest has one fewer edge than vertices in each component, giving the rank $|V|-\kappa (V,A)$. The matroid independence polytope theorem therefore proves the first description. It implies the second since the rank of $E(S)$ is at most $|S|-1$. Conversely, split any $A$ into its vertex components $S_j$; nonnegativity gives $x(A)\le {\sum }_{j}x(E(S_j))\le {\sum }_j(|S_j|-1)=|V|-\kappa (V,A)$. No spanning requirement is imposed, so an optimum with negative edge weights can leave vertices isolated.

For the degree-constrained linear programming relaxation of a matching in a graph, retain precisely the edges with fractional coordinates. In a bipartite graph, an even graph cycle in this subgraph permits alternating positive and negative perturbations preserving all vertex sums. If the subgraph is a forest, use a graph path between two tree leaves: its endpoints have positive slack and its internal sums remain unchanged. Either perturbation expresses the original feasible point as the midpoint of two distinct feasible points. Hence a fractional feasible point cannot be an extreme point, proving integrality of all extreme points of the bipartite degree relaxation.

For a finite simple graph on $n$ vertices with $m$ edges and no graph cycle shorter than $\ell$, the coefficient of $x^{n-i}$ in its chromatic polynomial is $(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})$ for $0\le i\le \min (n,\ell -2)$. In the chromatic polynomial inclusion-exclusion formula, an edge subset containing a graph cycle of length at least $\ell$ has $n-c(F)\ge \ell -1$. Thus every contribution to $x^{n-i}$ in this range is a forest, with exactly $i$ edges. Conversely, all $i$-edge subsets are forests, so precisely $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ terms contribute, each with sign $(-1{)}^i$.

For a finite undirected graph, the graphic matroid has its edges as the ground set. A subset is a matroid independent set when its edges form a forest on the original vertices, including isolated vertices. Its matroid bases give a spanning tree in each connected component of a graph; for a connected graph, each matroid basis is a spanning tree.

For a graph triangle on vertices $P,Q,R$, label the edges $a=PQ$, $b=QR$, and $c=PR$, with weights $8,5,6$. The empty set, all singletons, and all pairs are forests; the triple contains the graph cycle $P,Q,R,P$. Thus its eight subsets have exactly the independence pattern checked in the weighted three-vector matroid, and the same fifteen exchange comparisons pass. The matroid greedy algorithm chooses $PQ$, chooses $PR$, and rejects $QR$, producing the heaviest spanning tree, of weight $14$.

Exchange outline. Deleting edges cannot create a graph cycle. If forests $I,J$ have $|I|<|J|$, some edge of $J$ joins different connected components of a graph of $I$: otherwise, within each such component, $J$ would have at most its number of vertices minus one edges, giving $|J|\le |I|$. Adding that edge keeps a forest. This is the matroid independence axioms expressed through connectivity.

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]