Given a complete graph $G=K_{2n}$, construct a set $P$, such that each element $p$ of $P$ is a perfect matching of $G$ and every two elements $p_i,p_j$ don't share a common edge of $G$.What's the maximum cardinality of $P$?

I'd like to calculate the maximum number of perfect matchings of a complete graph of order $2n$, such that no edge appears in two different matchings and find an algorithm to construct one enumeration of such perfect matchings if possible.

I believe each such set could contain up to ${{2n}\choose{2} }/n = 2n-1$ perfect matchings, but I was unable to construct one or prove such enumeration must exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.