Maximum matchings in the \(n\)-dimensional cube (Q5951061)

It is proved that in an \(n\)-dimensional hypercube for every odd \(n\geq 3\) it is possible to find efficiently a maximal matching with \(m= {n\choose r}+ \sum_{i=\theta}^{(r-2+ \theta)/2} {n\choose 2i-\theta}\) edges, where \(r= (n-1)/2\) and \(\theta= 1\) if \(n\equiv 3\bmod 4\) and \(\theta= 0\) if \(n\equiv 1\bmod 4\).