# How many trees are in the spanning forest of a graph?

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?

• "I just read that a spanning forest of a graph is a set of spanning trees, one for each connected component of G." There's your answer --- the number of trees in a spanning forest is the number of connected components. "For a spanning tree to exist, doesn't it have to contain all vertices in the graph G?" Sure, but a spanning forest isn't the same thing as a spanning tree. – Gerry Myerson Apr 5 '14 at 11:11

You can apply the Matrix Tree Theorem to each connected component of $G$. Since the number of spanning trees in a given component is independent from the number of spanning trees in the other components, you simply multiply your results for each component together.