Matchings and Hall's Theorem · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Pair everyone or find the blocker

Mathematics · Discrete Mathematics · ages 21-22
Name ______________________   Date ____________

  1. Applicant A suits jobs X and Y. Applicant B suits job Y. Collect all jobs suited to at least one of A, B. How many distinct jobs are collected?

    Answer: ______________

  2. Applicants A, B, C seek jobs X, Y, Z. A suits X, B suits Y, C suits Z. How many pairs can be formed covering all applicants with distinct suitable jobs?

    • 2
    • 3
    • 4
    • 1

  3. Applicants A, B, C seek jobs X, Y, Z. A suits X, B suits Y, C suits Z. How many pairs cover all applicants?

    • 2
    • 3
    • 4

  4. Three students apply for two projects. A full pairing giving every student a different project is impossible.

    Circle one:   True   False

  5. You hold a partial pairing and one applicant is still free. How do you improve it?

    • Follow unused then used edges from an unmatched applicant and flip on reaching a free job
    • Delete one applicant and start over each time
    • Pair everyone with their first listed job

  6. Hall condition says each group of applicants must collectively suit at least as many jobs as there are applicants in the group. If this holds for every group, a pairing covering all applicants always exists in a finite bipartite graph. Is this sufficiency claim correct?

    Circle one:   True   False

  7. Applicants A, B, C seek jobs X, Y. A suits X, B suits X, C suits Y. Which group of applicants shows the Hall condition fails?

    • {A}
    • {C}
    • {B, C}
    • {A, B}

  8. A suits X, B suits X, C suits Y, with jobs X and Y. Which group shows Hall fails?

    • {A}
    • {C}
    • {A, B}

  9. Every group of applicants suits enough distinct jobs. Does a full pairing follow?

    • Yes, it guarantees a full pairing exists
    • No, it only shows one pairing attempt failed
    • Yes, it proves no jobs exist at all

  10. Applicants A, B, C seek jobs X, Y. A suits X, B suits X, C suits Y. What is the largest number of pairs with distinct suitable jobs?

    Answer: ______________

LightMySky · lightmysky.comW1-mt_hkWslW5b5U-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Pair everyone or find the blocker W1-mt_hkWslW5b5U-s1

  1. 2 · Union of suits is X and Y, which has size 2.
  2. 3 · 3 pairs work: A with X, B with Y, and C with Z cover everyone with distinct suitable jobs.
  3. 3 · A with X, B with Y, and C with Z covers everyone distinctly.
  4. True · Three students cannot fit into two distinct projects.
  5. Follow unused then used edges from an unmatched applicant and flip on reaching a free job · Flipping that alternating path grows the pairing by one each round.
  6. True · This is Hall theorem sufficiency, proved by induction or augmenting paths.
  7. {A, B} · {A, B} collectively suit only X, one job for two applicants, violating the Hall requirement, while the other listed groups meet it.
  8. {A, B} · A and B jointly suit only X, one job for two applicants, so Hall fails there.
  9. Yes, it guarantees a full pairing exists · Hall is both ways: holding everywhere is exactly what a full pairing needs.
  10. 2 · One of A, B takes X and C takes Y, giving 2 pairs, and 3 pairs are impossible with only 2 jobs.
Worksheet · LightMySky