MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

A network has two separate pieces with no links between them. The first has workers u1,u2,u3u_1,u_2,u_3 each linkable to either resource aa or resource bb. The second is a ring 1-2-3-4-5-6-11\text{-}2\text{-}3\text{-}4\text{-}5\text{-}6\text{-}1. How many different maximum independent sets (sets of this maximum possible size with no two chosen vertices linked) does the whole network have?