Part 2: Random Graphs A tournament T is a complete graph whose edges are all oriented. Given a complete graph on n vertices Kn, we can generate a random tournament by orienting each edge with probability 1 2 in each direction. Recall that a Hamiltonian path is a path that visits every vertex exactly once. A Hamiltonian path in a directed graph is a path that follows the orientations of the directed edges (arcs) and visits every vertex exactly once. Some directed graphs have many Hamiltonian paths.

Part 2: Random Graphs
A tournament T is a complete graph whose edges are all oriented. Given a complete
graph on n vertices Kn, we can generate a random tournament by orienting each edge
with probability 1
2 in each direction.
Recall that a Hamiltonian path is a path that visits every vertex exactly once. A
Hamiltonian path in a directed graph is a path that follows the orientations of the
directed edges (arcs) and visits every vertex exactly once. Some directed graphs have
many Hamiltonian paths.
In this part, we give a probabilistic proof of the following theorem:
Theorem 1. There is a tournament on n vertices with at least n!
2n−1 Hamiltonian paths.
For the set up, we will consider a complete graph Kn on n vertices and randomly
orient the edges as described above. A permutation i1i2 ...in of 1,2,...,n represents
the path i1 −i2 −···−in in Kn. We can make the path oriented by flipping a coin and
orienting each edge left or right: i1 ←i2 →i3 ←···→in.
(a) How many permutations of the vertices 1,2,...,n are there? Denote the set of all
permutations of 1,2,...,n by Sn.
(b) Consider a permutation π = i1i2 ...in of the vertices of G. What is the probability
that i1 →i2 →... →in is a path in a random tournament in G? Why?
Let X be the random variable from the set of tournaments on Kn to Rdefined by
X(T) = the number of Hamilton paths inT.
Let π be a permutation of 1,2,...,n. Define the random variable ˆX from permutations
of 1,2,...,n to R( ˆX : Sn →R) by
ˆX =
(
1, π is a Hamiltonian path in T
0, otherwise .
Then
X = X
π∈Sn
ˆX(π)
(the sum is over all permutations of 1,2,. . . , n).
(c) What is the expectation of X, that is, what is the expected number of Hamiltonian
paths in a random tournament? (Use linearity of expectations.)
(d) From the expectation of X found in (c), why can we conclude that there is a tour-
nament on n vertices with at least n!
2n−1 Hamiltonian paths?
Note that in this argument, we showed the existence of at least n!
2n−1 Hamiltonian
paths in some tournament but we did not construct the Hamiltonian paths, nor did we
even construct the tournament.