0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Gerry Myerson Apr 5 '14 at 11:11
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

http://en.wikipedia.org/wiki/Kirchhoff's_theorem

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.