The prism over Petersen's graph is Hamiltonian. Can you find two edge disjoint Hamiltonian cycles in this graph?
Edge disjoint Hamiltonian cycles
2
$\begingroup$
graph-theory
-
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
An example of the prism over the Petersen graph decomposing into Hamilton cycles:
A non-example (just to show that it's not always possible):
Here the green edges are a Hamilton cycle, whereas the black edges are not.
These were found via a computer search.