Question

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

Short answer

The number of spanning forests is r. The number of the connected component of the underlying finite graph.

Step-by-step solution

Definition

A path is called a simple path if it does not repeat the vertices.

Find a spanning-tree forest.

Consider a finite simple graph G with r connected components\({\bf{(}}{{\bf{G}}_{\bf{1}}}{\bf{,}}{{\bf{G}}_{\bf{2}}}{\bf{,}}.....{\bf{,}}{{\bf{G}}_{\bf{r}}}{\bf{)}}\),Since a simple graph is connected if it has a spanning tree, there exists a spanning tree of the components \({\bf{(}}{{\bf{T}}_{\bf{1}}}{\bf{,}}{{\bf{T}}_{\bf{2}}}{\bf{,}}.....{\bf{,}}{{\bf{T}}_{\bf{r}}}{\bf{)}}\)respectively.

According to the definition,

\(\bigcup\limits_{{\bf{i = 1}}}^{\bf{r}} {{{\bf{T}}_{\bf{i}}}} \)is a spanning tree forest of G.

Therefore, the number of spanning forests is r. The number of the connected component of the underlying finite graph.