Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n\ge 2$ be an even number and $0<k<n$ be an integer. What is the smallest number $x$ satisfying the following: If a simple graph with $n$ vertices has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings.

Necessary lower bounds for $x$ are easily found: eg. $x>\frac{(n-1)(n-2)}{2}$ ($n-1$ complete graph) or $x\ge \frac{nk}{2}$ ($\frac{n}{2}$ edges are needed for a perfect matching). A sufficient lower bound doesn't seem to be easily obtainable.

share|improve this question
Duplicate of (but a better phrasing than) math.stackexchange.com/questions/319402/… which hasn't been answered. –  Erick Wong Mar 11 '13 at 0:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.