Hall's Marriage Theorem - Discussion and Examples

Discussion and Examples

Example 1: Consider S = {A₁, A₂, A₃} with

A₁ = {1, 2, 3}

A₂ = {1, 4, 5}

A₃ = {3, 5}.

A valid SDR would be {1, 4, 5}. (Note this is not unique: {2, 1, 3} works equally well, for example.)

Example 2: Consider S = {A₁, A₂, A₃, A₄} with

A₁ = {2, 3, 4, 5}

A₂ = {4, 5}

A₃ = {5}

A₄ = {4}.

No valid SDR exists; the marriage condition is violated as is shown by the subcollection {A₂, A₃, A₄}.

Example 3: Consider S= {A₁, A₂, A₃, A₄} with

A₁ = {a, b, c}

A₂ = {b, d}

A₃ = {a, b, d}

A₄ = {b, d}.

The only valid SDR's are (c, b, a, d) and (c, d, a, b).