Thread: 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.

PLEASE HELP!!!

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 to the graph which is adjacent to every other vertex in the graph.

Now apply Dirac's theorem.

Originally Posted by Plato

Here is the usual hint: add a vertex 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. ]

Help Please!!!

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.

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!!!