2
$\begingroup$

A hamiltonian cycle is a cycle which visits each vertex of the graph exactly once.
A hamiltonian path is a path which visits each vertex of the graph exactly once.

We need to prove that:

1-$ \forall n \in N$ edges of $K_{2n+1}$ can be partitioned to hamiltonian cycles.

2-Then show that edges of a $K_{2n}$ can be partitioned to hamiltonian paths.

Note : We already know that every complete graph has a hamiltonian cycle. The problem here is that the question doesn't want just one cycle. I am not sure how to pove that such a partitioning exists.

Any help will be useful!

Thanks in advance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.