MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

A network has two separate pieces with no links between them: a 44-cycle 1-2-3-4-11\text{-}2\text{-}3\text{-}4\text{-}1, and a second, separate 44-cycle 5-6-7-8-55\text{-}6\text{-}7\text{-}8\text{-}5. How many different MINIMUM vertex covers does the whole network have?