Could a complete graph $K_{2n}$ be covered by perfect matchings with no same edge?

96 Views Asked by At

Consider a complete graph $K_{2n}$. I want to find a set of perfect matching, each of which has no same edges, to cover this graph (all edges could be contained in this set). Does this set exist?

Or in other words, each time I find a perfect matching in the graph and I delete the corresponding edges in the matching. Can I find a way that by repeating the procedure I could delete the whole graph (no edge left)?

I tried for $n=1,2$ and found it true. Is it true for $n=3,4,\cdots$?

Moreover, if it is true, is there a universal way to find the matchings?

2

There are 2 best solutions below

0
On

A theorem of Konig is that every bipartite graph has an edge coloring with as many colors as the maximum degree $\Delta$. Equivalently, every bipartite graph can be decomposed into $\Delta$ matchings. In particular, $K_{2n}$ can be decomposed into $n$ (perfect) matchings.

0
On

It seems to me that one can reason this way.

Let $\{a,b\}$ be the part of the graph $K_{2n}$ of two vertices.
Let $e_1,\ldots,e_n$ be edges going from vertex $a$ to vertices $v_1,\ldots,v_n$. Now take an arbitrary permutation $\pi$ of $S_n$ with the condition that $\pi(i)\neq i$ for each $i$. Let $f_1,\ldots, f_n$ be edges going from vertex $b$ to vertices $v_{\pi(1)},\ldots,v_{\pi(n)}$. Then $\{e_i,f_i\}$ are $n$ of perfect matchings.

Isn't it?