Forest (source code)
= Forest
= Acyclic graph
{synonym}
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> has
$$
|E|=n-c.
$$
Indeed, 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>. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec05-06.pdf[MIT, counting notes, p. 4: building forests by merging components]{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.
Back to article page
