MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

Five applicants 1,2,3,4,51,2,3,4,5 apply to jobs a,b,c,da,b,c,d as follows: 11 and 22 qualify only for aa; 33 qualifies for aa or bb; 44 qualifies for bb or cc; 55 qualifies for cc or dd. What is the maximum number of applicants who can be simultaneously placed into distinct jobs?