 Solution

ID: past-exam-of-the-probability-statistics-and-options-ii-course-of-the-university-of-oxford/2011/r/r2/b/solution

Represent the two sides of the marriage problem as the parts

L, R

of a bipartite graph, with an edge for each allowed pairing. A matching is a set of edges with no common endpoint; a complete matching of

L

covers every vertex in

L

. When the two parts have equal size it also covers

R

Hall's marriage theorem gives the exact finite-graph criterion:

∣ N (S) ∣ \geq ∣ S ∣ for every S \subseteq L .

Here

N (S)

is the set of right-side neighbours of

S

. Necessity follows because distinct matched vertices of

S

need distinct neighbours; Hall's theorem supplies sufficiency.

 New to topics? Read the docs here!