# Graph theory problem (edge-disjoint matchings)

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.

-
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

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.
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$.