MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

People P,Q,RP,Q,R are each qualified only for opening 11; person SS is qualified for openings {2,3}\{2,3\}; person TT is qualified for {4,5}\{4,5\} (five people, five openings 11–55). What is the minimum number of new qualifications (edges) that must be added so that all five people can be placed in distinct openings?