Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

Then, since there are no edges connecting 2 trees (or else they'd be part of the same tree), you can just sum all the edges from each tree to get the total number of edges.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.