A graph having a perfect matching is called r-extendable if every matching of size r can be extended to a perfect matching. It is proved that in the hypercube Qₙ, a matching S with |S|≤ n can be extended to a perfect matching if and only if it does not saturate the neighbourhood of any unsaturated vertex. In particular, Qₙ is r-extendable for every r with 1≤ r≤ n-1.
No takes yet. Share an insight, caveat, or question.
Limaye et al. (1997) studied this question.