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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Duplicate of (but a better phrasing than)… 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.