 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ii/paper-3/17f/i/solution

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

Write

r = n / m

\sum_{v} \frac{1}{d ( v ) + 1} \geq \frac{n ^{2}}{\sum _{v} ( d ( v ) + 1 )} = \frac{n ^{2}}{2 e ( G ) + n} = \frac{n ^{2}}{m r ( r - 1 ) + m r} = m .

The proved Caro-Wei bound therefore gives an independent set of at least $m$ vertices.

 New to topics? Read the docs here!