2
$\begingroup$

The prism over Petersen's graph is Hamiltonian. Can you find two edge disjoint Hamiltonian cycles in this graph?

  • 0
    @newday: I can't. I don't have free access to that paper, and I don't want to duplicate the work they did. But it looks like you should be able to find the answer in that paper. If not you can always get back here.2012-10-11

1 Answers 1

1

An example of the prism over the Petersen graph decomposing into Hamilton cycles:

Hamiltonian decomposition of the prism over the Petersen graph

A non-example (just to show that it's not always possible):

Not a Hamiltonian decomposition of the prism over the Petersen graph

Here the green edges are a Hamilton cycle, whereas the black edges are not.

These were found via a computer search.