MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

A 1010-item network has X={1,2,3,4,5}X=\{1,2,3,4,5\} and Y={a,b,c,d,e}Y=\{a,b,c,d,e\}: items 1,2,31,2,3 are each compatible only with aa or bb; item 44 is compatible with cc or dd; item 55 is compatible with dd or ee. What is the size of a maximum independent set among all 1010 items (the largest group with no compatibility link between any two of its own members)?