MathCastle
Graph TheoryEasyBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Easy problem

In a small village of eight people, residents 1,2,3,4,51,2,3,4,5 can each be paired with a well as follows: 11 and 22 can only use well aa; 33 and 44 can only use well bb; 55 can only use well cc (wells a,b,ca,b,c count as 33 more people in this network for a total of 88). What is the size of a maximum independent set — the largest group of these 88 "people" with no pairing possible between any two of them?