Graph Theory

• May 25th 2012, 09:03 AM
Sarasij
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.

• May 25th 2012, 09:23 AM
Plato
Re: Graph Theory
Quote:

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

Now apply Dirac's theorem.
• May 25th 2012, 09:28 PM
Sarasij
Re: Graph Theory
Quote:

Originally Posted by Plato
Here is the usual hint: add a vertex \$\displaystyle 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. ]

• May 26th 2012, 04:07 AM
Plato
Re: Graph Theory
Quote:

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.
• May 26th 2012, 07:41 PM
Sarasij
Re: Graph Theory
Quote:

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