Prove that for $n\ge 2$, the $n$-cube has at least $2^{2^{n-2}}$ perfect matchings

While reviewing graph theory, I came across a problem that I could not solve. The first part of the question asked one to prove that the n-cube has a perfect matching. This seemed to be a consequence of Hall's Theorem also described here:

Perfect matching in k-cubes

However, I am not sure as to how to start to enumerate how many perfect matching are in total. Any help would be much appreciated!

Thanks

It holds trivially for $n=2$. So we proceed by induction on $n$. If it holds for some $n\geq 2$, then we consider the $n+1$-cube which constitutes of $2$ $n$-cube, by induction hypothesis, each $n$-cube has at least $2^{2^{n-2}}$ many perfect matchings, hence, just consider those perfect matchings formed by some perfect matchings of the two $n$-cube, for the $n+1$-cube we have at least $(2^{2^{n-2}})^2=2^{2\cdot2^{n-2}}=2^{2^{(n+1)-2}}$ perfect matchings.

• I can't believe I missed this. Induction and contrapositives are the proof styles that I am finding really common for a lot of graph theory proofs. I will definitely take care to investigate approaches thoroughly before seeking help! Thanks! – stantheman Apr 1 '15 at 22:49
• At first sight I thought it would be harder, but after I tried the case $n=3$, I found the bound is very very loose, so I took an easy approach. – Salomo Apr 1 '15 at 23:11
• Very true observation. It seems that the bound gets really loose as n grows where for n = 7 it is 4 294 967 296 when the actual result according to this link is 391 689 748 492 473 664 721 077 609 089. – stantheman Apr 2 '15 at 2:07