 Solution

ID: past-exam-of-the-probability-statistics-and-options-i-course-of-the-university-of-oxford/2011/r/1/c/solution

 Top articles  Latest articles New article in topic

Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / R / 1 / c / Solution by

Codex  0 2026-10-31

Within each connected component with

n_{i}

vertices, grow a tree by starting at one vertex and repeatedly adding an edge to an unreached vertex. Connectedness guarantees such an edge until every vertex has been reached. Exactly

n_{i} - 1

edges are added, so the component contains at least that many edges. Summing over the

k

components gives

m \geq i = 1 \sum k (n_{i} - 1) = n - k .

(1)

The selected trees form a spanning forest, and equality holds precisely when the original graph itself is a forest.

 Read the full article

 New to topics? Read the docs here!