## Prove of every tournament has an odd number of Hamiltonian paths

First we define some symbols

• G is the directed graph we are going to look at
• H is the class of Hamilton path
• E(X) denotes the set of all edges of X
• e means an directed edge and $\bar{e}$ is the edge in the other direction.
• $\Pi_n$ means the set of permutations of 1 to n.
• $f(e,Y)=|\{P:P\in H,e\in E(P)\subseteq Y\}|$
• $g(X)=|\{\pi:\pi\in\Pi_n \exists i, (\pi(i),\pi(j))\in X\}|$

Now we look at G with n verticals.

It’s obvious that $f(\empty, E(G))$ is the number of Hamilton path of G and we know that for the graph G’ that $(i,j)\in E(G)$ iff i<j. And then if we prove that $f(\empty, E(G))\equiv f(\empty, E(G)-e+\bar{e} \mod 2$ for any $e\in E(G)$ then we can have the conclusion by induction.

So now what we want to prove is that $f(e,E(G))\equiv f(\bar{e},E(G)-e+\bar{e}) \mod 2$
And because of the repelling law we know that

$f(e,E(G))=\sum_{\{e\}\subseteq X\subseteq E(\bar{G})-\bar{e}+e}(-1)^{|X|-1}g(X)$

And g(X) is k! or zero, so g(X) is odd iff g(X)=1, and g(X)=1 iff X is an Hamilton path of n verticals.

So we know that $f(e,E(G))\equiv f(e,E(\bar{G})) \mod 2$
And it’s obvious that $f(e,\bar{G})=f(\bar{e},G)$
So we have proved the conclusion.