# Maximal number of perfect matchings that pairwise form a Hamiltonian cycle

Definition: Let $$MH(n)$$ be the maximal number of perfect matchings (1-regular graphs) on $$n$$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.

Question: Is it true that $$MH(N)=n-1$$ for infinitely many $$n$$?

Additional information: Needless to say that the problem makes sense only when $$n$$ is even. I needed in a proof that $$3 \leq MH(n)$$. This is true and not hard, but right now I can prove it by two simple constructions, one when $$n=4k$$ and an other when $$n=4k+2$$. So I am just curious what might be the maximal possible number.

It is easy to see that $$MH(N)\leq n-1$$ since the perfect matchings must be edge disjoint and there are not enough edges for more than $$n-1$$. It is very easy to see that $$MH(4)=3$$. But I was quite surprised when it turned out that $$MH(6)=5$$. See the picture for the construction, it is not hard to check that indeed every pairwise union forms a Hamiltonian path. So right now it is still possible that $$MH(n)=n-1$$ for all even $$n$$.

The 5 matchings on 6 vertices

• If you have $n-1$ of these one-factors, then you have a "perfect one-factorisation of the complete graph". My dated understanding is that it is an open question as to whether they exist for all even n, but searching on this phrase should help. Commented Dec 30, 2016 at 6:55
• @GordonRoyle Oh, so this is already studied and is called perfect one-factorisation. And indeed it seems to be open. Thank you very much! Should I delete the question? Commented Dec 30, 2016 at 7:02
• I don't think you need to delete, it would be interesting to know the state of the art. (But certainly they exist infinitely often.) Commented Dec 30, 2016 at 7:12

Assume that $n-1$ is an odd prime. Arrange the vertices as follows: $n-1$ of them lie on the circle and form a regular $(n-1)$-gon, and the $n$th vertex is the center. Now, each of the matchings consists of one radius and all the chords perpendicular to this radius.

Indeed, take any two matchings and remove the two radii. The remaining egdes form a graph with two vertices of degree 1 and all the rest of degree 2. Moreover, since $n-1$ is prime, it is easy to see that this graph contains no cycles (such cycle should pass through all the vertices which is impossible). Thus this graph is a path, and the radii complete a Hamiltonian cycle.

Right now I do not know what happens if $n-1$ is composite.