0

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.

user2553807
  • 1,245
  • 25
  • 46

2 Answers2

2

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.

Community
  • 1
AnalysisStudent0414
  • 8,173
1

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.

dshin
  • 1,525