Introduction to Graph Theory · Problem 7.2

Independent sets — Darij Grinberg

Mathematics — Graph Theory · tournaments-hamiltonian-paths-probabilistic

Problem

Let

n

be a positive integer. Prove that there exists a tournament with

n

vertices and at least

\dfrac{n!}{2^{n-1}}

Hamiltonian paths.