MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

Four interns 1,2,3,41,2,3,4 need desks: 11, 22, and 33 can each use desk aa or desk bb only, while 44 can use desk cc or desk dd. At first glance every PAIR of interns seems to share enough desks (any two of 1,2,31,2,3 have both aa and bb between them). Does a desk assignment exist that seats all four interns at distinct desks? If not, what is the maximum number that can be seated?