1. ## Graph Theory

The problem is as follows:
-------------------------------------------------------------------------------------------------------------------------
G=(V,E) is an undirected graph with |V|=n. If degree(vi)>n/2 for all i=1,2,...,n then prove that G must have a Hamiltonian Path.

2. ## Re: Graph Theory

Originally Posted by Sarasij
The problem is as follows:
-------------------------------------------------------------------------------------------------------------------------
G=(V,E) is an undirected graph with |V|=n. If degree(vi)>n/2 for all i=1,2,...,n then prove that G must have a Hamiltonian Path.
Here is the usual hint: add a vertex $u$ to the graph which is adjacent to every other vertex in the graph.

Now apply Dirac's theorem.

3. ## Re: Graph Theory

Originally Posted by Plato
Here is the usual hint: add a vertex $u$ to the graph which is adjacent to every other vertex in the graph.

Now apply Dirac's theorem.
Actually when I got this problem it said that Ore's theorem is to be proved here which I can't find anywhere. Please can you explain it a more and provide Ore's proof? It is necessary for this problem.

[*NOTE*: I guess you are confusing Ore's theorem with Dirac's theorem. The book from which I have got the problem said that this problem itself is Dirac's Theorem and Ore's theorem can be used to prove it which is as follows:

In a graph G with |V|=n , if d(vi)+d(vj)>=n then the graph has a Hamiltonian Circuit. ]

4. ## Re: Graph Theory

Originally Posted by Sarasij
Actually when I got this problem it said that Ore's theorem is to be proved here which I can't find anywhere. Please can you explain it a more and provide Ore's proof? It is necessary for this problem.
[*NOTE*: I guess you are confusing Ore's theorem with Dirac's theorem. The book from which I have got the problem said that this problem itself is Dirac's Theorem and Ore's theorem can be used to prove it which is as follows:
In a graph G with |V|=n , if d(vi)+d(vj)>=n then the graph has a Hamiltonian Circuit.
Different authors report different versions of Dirac's theorem.
I have reference to the original 1952 proof.

5. ## Re: Graph Theory

Originally Posted by Plato
I have reference to the original 1952 proof.
WOW man...this is awesome,please,is it possible for you to show me the original reference somehow?? Actually I like to see these rare original texts!!!

And anyways thanks a lot for showing the proof of the theorem!!!