Skip to content
Quantoros

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

Related questions