0
$\begingroup$

Assume you have a forest with k connected components. Prove that if you added $k$ edges, you would obtain a cycle.


I’m thinking these facts/theorems may be useful...

In a forest, each component is a tree so each tree of order $n$ must have $n-1$ edges.

If $F$ is a forest of order $n$ containing $k$ connected components, then $F$ contains $n-k$ degrees.


I’m just not sure how to prove that I am guaranteed to get a cycle by adding k edges.

$\endgroup$
2
$\begingroup$

First, note that if you add an edge to a tree, you obtain a cycle. You should already know that, but if you don't, see this question for a proof.

So you cannot add edges $(a,b)$ if $a$ and $b$ lie in the same connected component. There is only one other possibility, that you add edges connecting different components.

So any edge you add will reduce by $1$ the number of connected components of the forest. Note that what you obtain is still a forest!
Therefore you can only add $k-1$ edges before having a connected forest (i.e. a tree). If you add one more, you're guaranteed to have a cycle.

$\endgroup$
1
$\begingroup$

Adding an edge within a tree will create a cycle. And if you add an edge connecting components, you end up with a forest of $(k-1)$ connected components. Induction implies that adding the remaining $(k-1)$ edges will create a cycle.

$\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.