2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – stantheman Apr 1 '15 at 22:49
  • $\begingroup$ 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. $\endgroup$ – Salomo Apr 1 '15 at 23:11
  • 1
    $\begingroup$ 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. $\endgroup$ – stantheman Apr 2 '15 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.