Question

Show that every finite simple graph has a spanning forest.

Short answer

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

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, \(\bigcup\limits_{{\bf{i = 1}}}^{\bf{r}} {{{\bf{T}}_{\bf{i}}}} \) is a spanning tree forest of G.