Spanning forest is defined by the following definition:
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.
The question is:
How many trees are in the spanning forest of a graph?
I am not really getting the question. I know a forest can only contain trees. When the definition says "such that two vertices are in the same tree of the forest when there is a path in G between these two vertices".. if there is a path in G between the two vertices, isn't it already assumed that they are in the same tree since they cannot be disconnected?
I just read that a spanning forest of a graph is a set of spanning trees, one for each connected component of G. For a spanning tree to exist, doesn't it have to contain all vertices in the graph G? If it does, how could there be connected components? Doesn't that imply that parts of the graph G are disconnected, meaning it is impossible for a spanning tree of G in the first place?
Best Answer
You can think of each connected component as a graph by itself and talk about its associated spanning trees.
What it is saying is that you build a spanning forest by choosing a spanning tree from each connected component, therefore the number of trees in a spanning forest is the same as the number of connected components.