I was trying to prove a problem of Bondy Murthy Graph Theory book, i've seen the Maximal Forest
the problem was :
Let G be a graph and F a maximal forest of G. Show that $E(F) = V(G) − C(G).$
where C(G) is the number of cycles of Graph G, and V(G) is the number of vertices in Graph G, and E(F) is the Number of Edges which are in the Maximal Forest F
I have two idea about Maximal Forest, i don't know if they are true or not :
1 – Assume that the graph needs to be Connected and we need to find a tree, the problem would be like Minimum Spanning Tree and the number of Edges would be Equal to V(G)-1, which is not the satisfy the formula of the problem, for example we can imagine a empty graph
2 – Assuming that graph is not Connected, so it has different partitions and the could have cycles or not(which means they could have tree like structure or not), so what is the definition of Maximal Forest here ? if we want to make a forest of it we can remove the cycles in each partition, this could satisfy the formula E(F) = V(G) - C(G), but i can't see any kind of Maximal in this forest, it is just a Normal Forest
i would appreciate any help. i really need to know the exact definition of Maximal Forest
Best Answer
From the formula, they clearly mean that a maximal forest of $G$ consists of a set of spanning trees for each component in $G$.
Edit: I notice that you misinterpreted $C(G)$ as the number of cycles of $G$, when it should actually be the number of connected components of $G$.
So for a connected $G$, the maximal forest would just be a spanning tree, $C(G)=1$ and the formula is good.
In the case of the empty graph, $V(G)=C(G)=0$ so the formula again holds.