MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

Five applicants P,Q,R,S,TP,Q,R,S,T apply for five openings 1,2,3,4,51,2,3,4,5. P,Q,RP,Q,R are each qualified only for {1,2}\{1,2\}; SS is qualified for {3,4}\{3,4\}; TT is qualified for {4,5}\{4,5\}. What is the largest number of applicants who can each be placed in a distinct opening they are qualified for?