 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/17f/a/i/solution

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

Let the bipartition be

X ⊔ Y

. Counting edges from each side gives

k ∣ X ∣ = ∣ E (G) ∣ = k ∣ Y ∣,

∣ X ∣ = ∣ Y ∣ = n /2

. For

S \subseteq X

, the

k ∣ S ∣

edges leaving

S

all end in

N (S)

, while each vertex of

N (S)

receives at most

k

of them. Therefore

k ∣ S ∣ \leq k ∣ N (S) ∣,

and Hall's condition holds. There is a matching covering

X

n /2

. No matching can use more than one edge at each vertex, so this is maximal and

ν (G) = \frac{n}{2} .

 New to topics? Read the docs here!