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

2 Answers 2

It is well-known that $K_n$, with ${n \choose 2}$ edges, decomposes into $n-1$ edge-disjoint perfect matchings. Consider a graph $G$ with at least ${n - 1 \choose 2} + k$ edges. $G$ is missing at most $n-1-k$ edges from the complete graph, and each missing edge means we need to throw away at most one of the perfect matchings. Hence we have $n-1 - (n - 1 - k) = k$ edge-disjoint perfect matchings left.

This is best possible, since if we have a graph $G$ that's a $K_{n-1}$ with an additional vertex incident to $k$ other vertices, it has ${n-1 \choose 2} + k$ edges and at most $k$ perfect matchings.

share|improve this answer

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.