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.

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.