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