6
$\begingroup$

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle Graph on 2n vertices (i.e. a complete graph $K_{2n}$ without the cycle $C_{2n}$).

I can verify this relationship, but it seems very arbitrary to me. Unfortunatly, OEIS does not give further details.

Why are these number of these two properties (inequivalent Hamiltonian Cycles and Perfect Matchings, respectively) equivalent in these two different objects (n-dimensional Octahedron and Complement of Cycle Graph $C_{2n}$)?

And hint or reference to the literature is very much apprechiated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

The $n$-dimensional analogue of the octahedron is the complement of a perfect matching of its vertex set. (Every vertex is joined to every other vertex except its antipode.) If you take a Hamilton cycle in the $n$-dimensional octahedron then you can think of that as a labelling of the $2n$-cycle, and the non-edges of the $n$-octahedron give a perfect matching of the complement of this graph.

This paragraph was added in answer to Nicodean's comment below. Label the vertices of the $n$-dimensional octahedron $1^+,1^-,...,n^+,n^-$, where the vertices $i^+$ and $i^-$ are antipodes. A labelled Hamilton cycle in the octahedral graph is then exactly a $2n$-cycle made from the $2n$ symbols $i^+,i^-$ with the property that the symbols $i^+$ and $i^-$ are never adjacent. Giving a perfect matching on the complement of a $2n$-cycle is the same as giving a matching of the elements of a $2n$-cycle so that adjacent elements are never matched. To do this, I choose the symbols making up my matching to be the symbols $1^+,1^-,...,n^+,n^-$, where the symbols $i^+$ and $i^-$ are pairs that are matched. The condition that adjacent symbols are never matched is exactly the same condition that I had on the $2n$-cycles that describe the Hamilton cycles in the $n$-octahedral graph.

One reason why this seems hard is that the matching sort of stays the same, while the $2n$-cycle whose complement it lives in is the thing that changes when you change the Hamilton cycle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you for your insights about the complement graphs. I still don't understand why these numbers should be the same. I understand that the complement of octahedron-graph gives one perfect matching, and the complementary of the ($K_{2n}-C_{2n}$), so the $C_{2n}$ gives one Hamiltonian cycle. But i do not understand why, for example, the n=3-dimensional octahedron graph has 4 Hamilton cycles, while the $K_{6}-C_{6}$ graph has 4 perfect matchings. Could you please explain your intuitions a bit more, or refere to some relevant literature? thank you! $\endgroup$
    – Mario Krenn
    Commented Jun 13, 2018 at 9:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .