En anglais

Pair everyone or find the blocker

Mathematics · Discrete Mathematics · ages 21-22

Name ______________________ Date ____________

A group S contains five left vertices. What is the smallest value of |N(S)| that passes Hall's check for this group?
Answer: ______________
Left vertices K and L are each adjacent to right vertices U and V. Which set of two edges is a matching?
- {K-U, K-V}
- {K-U, L-V}
- {K-U, L-U}
- {L-U, L-V}
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
Three students apply for two projects. A full pairing giving every student a different project is impossible.
Circle one: True False
A partial matching leaves an applicant unmatched. If an augmenting path from that applicant exists, how can you increase the matching?
- Flip an alternating path to an unmatched job
- Keep the matching fixed and discard the free applicant
- Choose each applicant's first job even when it is taken
J suits M and N, K suits only M, and L suits only O. Matching J to M and deleting J and M leaves a graph that still satisfies Hall's condition.
Circle one: True False
P and Q each suit jobs R and S. T suits jobs S and U. Which left-covering matching assigns distinct jobs to the tight group {P, Q} and to T?
- P takes R, Q takes U, T takes S
- P takes S, Q takes S, T takes U
- P takes R, Q takes S, T takes U
- P takes R, Q takes S, T takes S
A suits X, B suits X, C suits Y, with jobs X and Y. Which group shows Hall fails?
- {A, C}
- {B, C}
- {A, B}
Assume Hall's condition in a finite bipartite graph. Choose a largest matching M and suppose it leaves a left vertex unmatched. Which argument rules this out?
- Augmentation contradicts largest size; exhaustive search failure contradicts Hall.
- Hall gives each left vertex a neighbour, so independently chosen neighbours cannot repeat a right vertex.
- Having no edge that can be added makes a matching maximum, so an alternating search is unnecessary.
Applicants K,L,M,N seek jobs U,V,W,Z. K suits U; L suits U,V; M suits V; N suits W,Z. What is the maximum number of matched pairs?
Answer: ______________

Answer key

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

Pair everyone or find the blocker W1-mt_hkWslW5b5U-s1

5 · Hall requires |N(S)| >= |S|. Since |S|=5, the smallest passing value is 5.
{K-U, L-V} · {K-U, L-V} uses each endpoint once. The other sets repeat K, U or L.
3 · A takes X, B takes Y, and C takes Z, so everyone gets a different suitable job.
True · Three students cannot fit into two distinct projects.
Flip an alternating path to an unmatched job · An augmenting path starts and ends unmatched. Replacing its matched edges with its unused edges increases the matching by one pair.
False · After deleting J and M, K has no neighbour. The remaining singleton {K} violates Hall. The original graph has the left-covering matching J-N, K-M, L-O.
P takes R, Q takes S, T takes U · {P,Q} has exactly neighbours R and S, so it must use both. T must take U. The pairs P-R, Q-S and T-U are suitable and distinct.
{A, B} · A and B jointly suit only X, one job for two applicants, so Hall fails there.
Augmentation contradicts largest size; exhaustive search failure contradicts Hall. · Search from the unmatched left vertex. An augmenting path contradicts M's largest size. Exhaustive failure gives a set S with |N(S)|<|S|, contradicting Hall. Thus M covers the left side.
3 · {K,L,M} has only neighbours U,V, so at least one applicant stays unmatched and every matching has at most three pairs. K-U, M-V and N-W attain three.