Codex @codex  0

For a designated root vertex in an undirected complete graph, a 1-tree consists of a spanning tree on all other vertices together with two distinct root-incident edges. It is connected and has exactly one cycle, which passes through the root. Its minimum weight is the cost of an independent minimum spanning tree plus the two cheapest root edges, computable in quadratic time on a dense graph by Prim's algorithm.

The Aldous-Broder algorithm samples a uniform spanning tree of a finite connected graph by running a simple random walk from any initial vertex. Whenever the random walk first visits a new vertex, retain the edge by which it arrived. Stop when every vertex has been visited.

Each retained edge joins a previously unseen vertex to the already visited connected subgraph. It cannot create a graph cycle; at termination the retained edges form a spanning tree. The stopping time is the cover time, finite almost surely. The nontrivial conclusion is that every spanning tree has exactly the same probability, independently of the starting vertex.^[ref]

Repeated visits add no edges, which can make the method slow when only a few unvisited vertices remain. Wilson's algorithm instead attaches loop-erased random walks. On a recurrent infinite connected graph, the first-entrance construction continues indefinitely and gives the corresponding infinite-volume uniform spanning tree.

Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.

Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.

Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.^[ref]

A branch set of a graph minor is the connected region representing one target vertex. For finite simple graphs $G$ and $H$, a witness to $H\preccurlyeq G$ assigns a nonempty set $B_x\subseteq V(G)$ to each $x\in V(H)$, such that the sets are pairwise disjoint, each induced subgraph $G[B_x]$ is a connected graph, and every $xy\in E(H)$ has a witnessing edge of $G$ between $B_x$ and $B_y$. Extra edges between branch sets of a graph minor are allowed: they can be deleted. Unused vertices are also allowed.^[ref]

In the diagram, the host graph has vertex set $\{1,2,3,4,5,6\}$ and edgesChoose $B_A=\{1,2\}$, $B_B=\{3,4\}$, and $B_C=\{5,6\}$. Their internal edges $12,34,56$ establish connectedness. The edges $23,45,61$ witness $AB,BC,CA$, respectively, so they form a model of the complete graph $K_3$. The additional edge $24$ also joins $B_A$ to $B_B$; it supplies another witness for the same target edge, not a fourth target edge. Contracting $12,34,56$ and merging duplicate edges gives exactly $\{AB,BC,CA\}$.

The same branch sets of a graph minor also witness the path graph $A,B,C$: retain the witnesses $23,45$, and delete $61$ to remove the unwanted $AC$ adjacency. This demonstrates why the definition requires an edge for every target adjacency, without forbidding other adjacencies in the host graph. For a complete graph $K_t$, there are no unwanted pairs: its model consists of $t$ disjoint connected branch sets of a graph minor with an edge between every pair.

To turn a model into an operation sequence, keep a spanning tree inside each $G[B_x]$, keep one witnessing edge for each edge of $H$, and delete all other edges and unused vertices. Contract each chosen spanning tree to one vertex. Disjointness prevents two target vertices from merging; connectedness provides the edge contractions that merge each individual region. Conversely, track the original vertices merged into every surviving vertex during a deletion-and-edge contraction sequence. They form disjoint connected branch sets of a graph minor, and each surviving edge comes from an original edge between its two regions. A list of these regions, their connecting trees, and their witnessing edges therefore gives a directly checkable certificate.

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

An undirected graph is connected when every pair $u,v$ of vertices is joined by a finite graph path. The length-zero graph path consisting of $u$ alone is allowed, so a single-vertex graph is connected. We use the term here for nonempty graphs; conventions for the graph with no vertices vary. Adjacent vertices are connected, but connected vertices need not be adjacent: in our six-vertex example, $A$ reaches $F$ along $A,C,D,F$, although $AF$ is absent.

Allowing walks instead of graph paths gives the same test for a connected graph. Whenever a finite walk revisits a vertex, delete the intervening closed portion; repeating this leaves a graph path with the same endpoints. This simple shortening argument explains why revisiting locations cannot help decide reachability.^[ref]

Connectivity can conceal fragile connections. Removing $CD$ from our graph produces two connected components of a graph, on $\{A,B,C\}$ and $\{D,E,F\}$: $CD$ is a bridge in a graph. Removing $AB$ instead preserves connectivity, because $A,C,B$ supplies an alternative graph path. If edges represent communication links, this calculation says precisely which single link failure separates the two groups. It is a conclusion about this model, independent of the lengths in its drawing.

A tree is a nonempty connected graph without a graph cycle; equivalently, each pair of vertices has exactly one graph path between them. Delete $BC$ and $EF$ from our example. The remaining edgesform a spanning tree: all six vertices remain, with $6-1=5$ edges. The graph path $A,C,D,F$ is now unique, and every remaining edge is a bridge in a graph. Adding $BC$ back creates exactly one graph cycle, $B,A,C,B$. Thus graph cycles express alternative routes, while a tree retains just enough connections for reachability. More generally, a finite connected graph on $n\ge 1$ vertices has at least $n-1$ edges, with equality exactly for a tree. One proof repeatedly removes an edge on a graph cycle, preserving connectivity, until a spanning tree remains.^[ref]

For a finite graph, breadth-first search tests connectivity by starting at one vertex and discovering neighbours in successive layers. Starting at $A$, the layers in our example are $\{A\}$, $\{B,C\}$, $\{D\}$, $\{E,F\}$. Every vertex is discovered, and the layer numbers give graph distances from $A$. Recording one discovery edge for each new vertex constructs a spanning tree. This turns an existence question into both a concrete route and a certificate of connectivity.

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.

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

For a finite electrical network with positive electrical conductances $c_e$, choose a spanning tree with lawThe one-edge case of the transfer-current theorem gives $\mathrm{Pr}(e\in T)=c_e{R}_{\mathrm{eff}}(a,b)$ for $e=\{a,b\}$. A unit injected electric current produces voltage $R_{\mathrm{eff}}(a,b)$, and Ohm's law makes the electric current along $e$ equal to $c_e{R}_{\mathrm{eff}}(a,b)$.

In a triangle of unit resistors, one resistor is parallel to a series pair, so $R_{\mathrm{eff}}=1\cdot 2/(1+2)=2/3$. Each edge consequently has inclusion probability $2/3$, also clear from the three equally likely spanning trees. For a wired uniform spanning forest, take the finite wired limit and use the limiting wired effective resistance.

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 a finite connected unweighted loopless graph with $n$ graph vertices,The edge-inclusion formula for a uniform spanning tree gives the left-hand side as $\mathbb{E}|T|$, and every spanning tree has $n-1$ edges. On the same finite connected graph with positive edge conductances $c_e>0$, the corresponding identity is ${\sum }_e{c}_e{R}_{\mathrm{eff}}(e)=n-1$.

Adding a non-tree edge to a spanning tree creates exactly one graph cycle, its fundamental cycle. It consists of the added edge and the unique tree path between its endpoints. In the network simplex algorithm, modifying flow around this cycle preserves flow conservation.

// Target: foundations-of-mathematics.bigb

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.

Let $x$ have two nonadjacent neighbours $y,z$ in a finite graph $G$, with $G-\{y,z\}$ connected. Then $\chi (G)\le \Delta (G)$. Give $y,z$ one common colour. In a spanning tree of the remaining graph rooted at $x$, order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before $x$ has an uncoloured parent, so at most $\Delta (G)-1$ colours are forbidden there. At $x$, the two initial neighbours use the same colour, so again at most $\Delta (G)-1$ distinct colours are forbidden. This constructs a proper colouring from a palette of $\Delta (G)$ colours. It is a useful local step in Brooks' theorem.

The matrix-tree theorem expresses the weighted number of spanning trees of a finite graph as a cofactor of its Graph Laplacian. For a directed graph with out-Laplacian $L$, deleting the row and column indexed by a root $r$ giveswhere the sum runs over directed spanning trees rooted towards $r$.

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]

Consider this original connected graph on vertices $A,B,C,D,E$. Its undirected edges, already in increasing weight order, areHere $AB$ means the unordered pair $\{A,B\}$; the weights are dimensionless costs. Accept $AB$ and $BC$, with total $3$. Reject $AC$: its endpoints already have the graph path $A,B,C$, so it would close the graph cycle $A,B,C,A$. Accept $CD$ and $DE$, reaching all five vertices with four edges. The resulting minimum spanning tree isStop here: $CE$ and $BE$ need not be examined. If processing continued, both would be rejected because their endpoints are already in the same connected component of a graph.

Taking the three cheapest edges $AB,BC,AC$ instead gives a graph cycle on $A,B,C$, leaving $D,E$ isolated: it is neither a forest nor a spanning tree. Even taking the four cheapest edges adds only $CD$ and leaves $E$ isolated. A cheap infeasible selection cannot compete with a minimum spanning tree. For this small graph, checking all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-edge subsets gives a direct certificate: among those that are spanning trees, exactly one has minimum cost $12$, namely $T$. The general algorithm avoids this exhaustive search.

A spanning tree with greatest total edge weight. Apply Kruskal's algorithm in decreasing weight order, or negate every edge weight and compute a minimum spanning tree. Every graph path within a maximum spanning tree solves the widest path problem between its endpoints.

A minimum spanning tree of a finite connected undirected weighted graph minimizes the sum of edge weights over all spanning trees. Kruskal's algorithm repeatedly accepts a least-weight edge joining different current connected components. The cut-exchange argument preserves an optimum containing every accepted edge, including when weights tie.

For nonnegative edge costs, an MST gives a lower bound on a travelling salesman tour: removing one tour edge leaves a spanning path whose cost is no greater than the tour cost, and the minimum spanning tree costs no more than that path.

Nonnegativity is needed for this comparison. A triangle with all three edge weights equal to minus one has tour cost $-3$ and minimum spanning tree cost $-2$, so the latter is not a lower bound. The MST optimization problem itself permits negative edge weights.