MathCastle
Graph TheorySuperchallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Superchallenge problem

A network has three separate pieces with no links between them: a 44-cycle 1-2-3-4-11\text{-}2\text{-}3\text{-}4\text{-}1, a 66-cycle 5-6-7-8-9-10-55\text{-}6\text{-}7\text{-}8\text{-}9\text{-}10\text{-}5, and a piece where u1,u2u_1,u_2 are each linkable to any of p,q,rp,q,r. Treating everyone as 1515 vertices, what is the largest number of them that can be chosen so that no chosen vertex is linked to another chosen vertex?