6
$\begingroup$

A tournament is defined as an orientation of a complete graph. Prove or disprove the following statement:

In a tournament, there are exactly an odd number of Hamiltonian paths.

In all cases I’ve tried, the statement seems true, so I guess it’s always true. But to prove it, I really got confused. Two ideas have come up but get nowhere. Please help.

  1. Induction on number of vertices;
  2. Show that changing the direction of one edge won’t change the parity.
$\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.