Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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

share|improve this question
2  
See Question 1 here for a reference. – joriki Oct 10 '12 at 18:23
+1 Interesting. How does this graph look like? – draks ... Oct 10 '12 at 18:37
1  
@draks: take two copies of the Petersen graph and add an edge from each vertex in one copy to the corresponding vertex in the other copy. The result has 20 vertices, each of degree 4. – MJD Oct 10 '12 at 19:19
ahh, a prism, got it, thanks. – draks ... Oct 10 '12 at 19:21
@joriki could you give me an answer in more detail, plz.. Thanks! – newday Oct 11 '12 at 5:00
show 1 more comment

1 Answer

up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.