MathCastle
Graph TheoryMediumBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Medium problem

Eight items sit in a network: items 11 and 22 can each only be paired with item aa; items 33 and 44 can each only be paired with item bb; item 55 can only be paired with item cc (and a,b,ca,b,c are 33 more items in the network, for a total of 88). What is the size of a maximum independent set among all 88 items (the largest group with no possible pairing between any two of its members)?