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!!!
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!!!
Different authors report different versions of Dirac's theorem.
I have reference to the original 1952 proof.