Forest

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.

A forest whose connected components of a graph are star graphs. In an inclusion-minimal edge cover, every edge has at least one endpoint of vertex degree one, forcing this structure with no isolated vertex.

A two-component spanning forest of a finite connected graph is an acyclic spanning subgraph with exactly two connected components of a graph. It has $|V|-2$ edges. For distinct terminals $a,z$, a separating two-component forest places them in different components. Deleting an edge of the $a$-to-$z$ graph path of a spanning tree produces such a forest; adjoining any original edge across its cut reverses this operation. This is the counting correspondence behind the mean spanning-tree path current.

A forest containing one minimum spanning tree of each connected component of a graph of a finite undirected weighted graph, including isolated vertices. For disconnected input, Kruskal's algorithm returns a minimum spanning forest.

Among all acyclic graphs contained in a finite weighted undirected graph, with no requirement to connect vertices, one optimum is obtained by keeping only strictly negative edges and computing their minimum spanning forest. Removing a nonnegative edge never worsens weight or creates a cycle. Within a connected component of the negative-edge subgraph, any disconnected candidate forest can be extended by a negative crossing edge, strictly improving its weight. Hence an optimum must span each such component and minimise its tree weight. Kruskal's algorithm on the negative edges therefore solves the problem. Zero-weight edges are optional when they preserve acyclicity.