1
$\begingroup$

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.

$\endgroup$

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.