MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

A relay network has a 55-station ring 0-1-2-3-4-00\text{-}1\text{-}2\text{-}3\text{-}4\text{-}0, with an additional chain of stations 5,6,7,85,6,7,8 hanging off station 44 (links 45,56,67,7845,56,67,78). What is the size of a maximum matching (disjoint active links, no station in more than one)?