MathCastle
Graph TheoryChallengeBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Challenge problem

A network of 1515 devices splits into four pieces with no links between pieces: a 44-cycle on 44 devices, a 66-cycle on 66 devices, a path of 33 devices (so 22 links), and a single linked pair. In how many different ways can every device be labeled AA or BB so that every link joins an AA-device to a BB-device?