 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-2/17g/a/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

A tree is a connected acyclic graph; acyclic means containing no cycle. Every component of an acyclic graph is a tree. If the component orders are

n_{i}

, each has

n_{i} - 1

edges, so with

c \geq 1

components,

e (G) = i \sum (n_{i} - 1) = n - c \leq n - 1.

 New to topics? Read the docs here!