MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

The 33-dimensional hypercube graph Q3Q_3 has vertices {0,1}3\{0,1\}^3 with an edge between any two strings differing in exactly one coordinate (1212 edges total). How many perfect matchings does Q3Q_3 have (as a spanning subgraph using every vertex exactly once)?