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.

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even number greater than $k$).

*It means you find $k$ matchings which are pairwise edge-disjoint.

share|improve this question
What's the meaning of $k$ being variable? Why is this not the same if you replace $k$ by $1$? –  joriki Mar 3 '13 at 12:13
You're offering a bounty for someone to do your homework? –  Rahul Mar 11 '13 at 8:07

1 Answer 1

Here's an answer for the case $k=1$, perhaps you can build on it. The example $K_{n-1}$ (plus an isolated vertex) shows that $x > {n-1\choose 2}$. Suppose now that $e(G) > {n-1\choose 2}$, so that $e(G^c) < n-1$.

For each edge $e$ in the complement $G^c$, there are $(n-3)!! = (n-3)(n-5)\cdots 1$ perfect matchings of $K_n$ which pass through $e$. But there are $(n-1)!!$ perfect matchings altogether, and since $(n-1)!! > (n-3)!! e(G^c)$, there must be some perfect matching of $K_n$ that does not contain any edge of $G^c$, hence is a subgraph of $G$.

share|improve this answer

Your Answer


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

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