2
$\begingroup$

Stumbled upon this question in a practice problem set:

Suppose graph $G$ is a forest with $n$ vertices, $m$ edges and $T$ trees. Express $m$ in terms of $n$ and $T$.

I know that a simple graph is $G=(V,E)$, but I don't know where to go from here.

Any tips would be appreciated!

$\endgroup$
  • 3
    $\begingroup$ Hint: First think about how many edges are in a tree with $n$ vertices. Then think about what happens when you remove an edge. Use induction. $\endgroup$ – Jair Taylor Apr 11 '18 at 7:28
  • 1
    $\begingroup$ I'd also recommend just drawing out examples of forests and trying to find a pattern. $\endgroup$ – Jair Taylor Apr 11 '18 at 7:29
3
$\begingroup$

Consider a forest $G$ of $n = 10$ vertices and $m$ edges and $t = 3$ trees (say $T_1, T_2, T_3$). We want to solve for $m$.

To do this, we construct a new graph $G'$ from $G$ by drawing an edge from $T_1$ to $T_2$ and drawing an edge from $T_2$ to $T_3$. Observe that $G'$ now has $n' = 10$ vertices and $m' = m + 2$ edges but only $t' = 1$ tree (can you see why $G'$ is connected and acyclic?). It follows that $m' = 9$ so that $m = 7$.

Can you see how to generalize this argument?

$\endgroup$
  • $\begingroup$ yea i think i can see it, thanks! $\endgroup$ – nickoba Apr 13 '18 at 1:34

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.