1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is super awesome. My only question is where does the $n$ in $n_{i}$ come from? $\endgroup$ – Auston Jun 19 '15 at 15:59
  • $\begingroup$ Nevermind, it comes from here: "Suppose each component has $n_{i}$ vertices with $n_{i}$ ≥1" $\endgroup$ – Auston Jun 19 '15 at 16:08
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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