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.

Solutions Collecting From Web of "Graph theory problem (edge-disjoint matchings)"

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