Prove of every tournament has an odd number of Hamiltonian paths

Posted on May 8, 2010 by

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.

About these ads
This entry was posted in math and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s