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 is the edge in the other direction.
- means the set of permutations of 1 to n.
Now we look at G with n verticals.
It’s obvious that is the number of Hamilton path of G and we know that for the graph G’ that iff i<j. And then if we prove that for any then we can have the conclusion by induction.
So now what we want to prove is that
And because of the repelling law we know that
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
And it’s obvious that
So we have proved the conclusion.