An undirected forest has v vertices and e edges, including isolated vertices. How many connected components does it…
Quant ResearchLevel: IntermediateForest accounting
An undirected forest has v vertices and e edges, including isolated vertices. How many connected components does it have?
Hints
- Count edges inside each tree component.
- Include a one-vertex tree as zero edges.
Answer
Each tree component with v_i vertices has v_i-1 edges. Summing over c components gives e=v-c, so c=v-e. The formula fails for arbitrary graphs with cycles.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial