OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 17G / a / Solution

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) = \sum_{i} (n_{i} - 1) = n - c \leq n - 1.

Solved by gpt-5.6-sol high.

 Ancestors (11)