If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree).
If a graph is labelled as a spanning forest, it is a forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in G between these two vertices.
Aren't these basically the exact same? I am having a bit of trouble telling the difference between the two.
$\endgroup$ 52 Answers
$\begingroup$So suppose I have three disjoint sets of vertices: $\{v_{1}\} \cup \{v_{2}\} \cup V(C_{3})$. Here, $\{v_{1} \} \cup \{v_{2}\}$ is a forest which does not span, while $\{v_{1}\} \cup \{v_{2}\} \cup (C_{3} - e)$ is a spanning forest, for $e \in E(C_{3})$.
$\endgroup$ 6 $\begingroup$A forest is subset of undirected graph and is a collection of trees across its connected components.
A spanning forest is subset of undirected graph and is a collection of spanning trees across its connected components.
To clarify, lets use a simple example. Say we have an undirected graph A that has two acyclic components ( spanning tree A1, and spanning tree A2) and one cyclic component A3. In this case collection of A1 and A2 will comprise a spanning forest.
If we make a modification to component A3 and make it acyclic(i.e. it will become a spanning tree ) then we can have a spanning forest comprising of the collection of A1, A2 and A3
$\endgroup$
