 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/ii/paper-1/17j/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

For

S \subseteq X

, count with reciprocal degrees. On every edge

x y

d (x) \geq d (y)

, so

∣ S ∣ = \sum_{x \in S} \sum_{y \sim x} \frac{1}{d ( x )} \leq \sum_{y \in N (S)} \sum_{x \in S x \sim y} \frac{1}{d ( y )} \leq ∣ N (S) ∣.

Hall's condition holds, so Hall marriage theorem supplies the matching.

 New to topics? Read the docs here!