**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](https://i.stack.imgur.com/63htv.jpg)



Maximal number of perfect matchings that pairwise form a Hamiltonian cycle
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.


