I'm unable to fully understand how a graph could have many forests. I understand that a forest is a graph that has no circuits. So basically what I understood is that we call a graph a forest if it is not connected and it contains no circuits. But then how to generate a forest from a graph?? Do we make a tree for each connected component? If so, do we then call all the generated trees as the forest of the graph OR the forests of the graph?
[Math] Generating forests from a graph
graph theory
Related Solutions
Hint. Let $G$ be a graph which is the union of $k$ forests. (By the way, since a subgraph of a forest is a forest, each subgraph of $G$ is also the union of $k$ forests.)
(a) Find an upper bound (in terms of $k$ and $n$) for the size (number of edges) of $G$.
(b) Find an upper bound for the average degree of a vertex in $G$.
(c) Show that $\delta(G)\le2k-1$. ($\delta = $minimum degree.)
(d) Show that $\chi(G)\le2k.$ Use induction on the number of vertices, unless "degeneracy" has been covered. [P.S. Oops, I just noticed that you mentioned degeneracy in your question! I apologize for my careless reading!]
Spoilers:
An $n$-vertex forest has at most $n-1$ edges. Since $G$ has $n$ vertices and is the union of $k$ forests, $G$ has at most $k(n-1)$ edges. Hence the degree-sum of $G$ is at most $2k(n-1)$, and the average degree is at most $\dfrac{2k(n-1)}n=2k-\dfrac{2k}n\lt2k$. Since the average degree is less than $2k$, there must be a vertex of degree less than $2k$. Let $v$ be a vertex of degree less than $2k$. By the induction hypothesis, the graph $G-v$ is $2k$-colorable. Since $v$ is adjacent to at most $2k-1$ vertices in $G-v$, there is at least one color available for $v$.
This argument only applies to a finite graph $G$, but the theorem is also true for infinite graphs; the infinite case follows from the finite case by the De Bruijn–Erdős theorem.
"Spanning" is the difference: a spanning subgraph is a subgraph which has the same vertex set as the original graph. A spanning tree is a tree (as per the definition in the question) that is spanning.
For example:
has the spanning tree
whereas the subgraph
is not a spanning tree (it's a tree, but it's not spanning). The subgraph
is also not a spanning tree (it's spanning, but it's not a tree).
Best Answer
Graphs usually have many forests as subgraphs. How to make them? Delete some vertices and/or edges: if there's no cycles, it's a forest.
For example, this disconnected graph
has the forests
(which happens to have a spanning tree in each connected component) and
as subgraphs. [In fact, the two subgraphs above happen to be spanning forests (in the sense that the forest and the original graph have the same vertex set). However, it can also be useful to define "spanning forest" to mean having a spanning tree in each connected component.]
It contains non-spanning forests, such as
and it even contains forests without any edges, such as
and