# a forest, its subgraphs, components, number of edges

On our practice exam, our teacher gave us this problem and this solution:

Let $G$ be a forest with $k \geq 1$ components. What type of (sub)graph is each component? Suppose each component has $n_i$ vertices with $n_i \geq 1$. How many edges does $G$ have? (Show your work!)

ANSWER: Each component is a tree. Suppose there are $c$ components. Then $|E(G)| =\sum_{i=1}^c n_i − 1 = |V(G)| − c$.

I am confused as to how she got that answer. I do not understand how she knows to use that summation for the number of edges.

If $T$ is a (nonempty) tree, then you always have one more vertex than you do edges: $$\tag{*}|E(T)| = |V(T)| - 1.$$ Suppose that $T_1,\ldots, T_c$ are the different components of $G$. Then the number of edges in $G$ is the same as the number of edges in all of the $T_i$ combined, i.e., $$|E(G)| = \sum_{i=1}^c |E(T_i)|.$$ Here we use the formula ($*$) and get that $$|E(G)| = \sum_{i=1}^c |V(T_i)| - 1 = \sum_{i=1}^c n_i - 1.$$ That is where the formula came from.
• This is super awesome. My only question is where does the $n$ in $n_{i}$ come from? – Auston Jun 19 '15 at 15:59
• Nevermind, it comes from here: "Suppose each component has $n_{i}$ vertices with $n_{i}$ ≥1" – Auston Jun 19 '15 at 16:08
A tree with $n_i$ vertices has $n_i-1$ edges. If you haven't already learned this, it should be relatively easy to prove by induction. Two vertices obviously requires 1 edge. Then for the inductive step, take your tree of k vertices and add another vertex. The new vertex isn't yet connected to the other vertices yet, so add one edge from the new vertex to any of the other k vertices to correct it. Adding any more would create a cycle.