Results 1 to 5 of 5

Math Help - Graph Theory

  1. #1
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    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!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Graph Theory

    Quote Originally Posted by Sarasij View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Graph Theory

    Quote Originally Posted by Plato View Post
    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. ]

    Help Please!!!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Graph Theory

    Quote Originally Posted by Sarasij View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member Sarasij's Avatar
    Joined
    Jun 2011
    From
    India
    Posts
    42
    Thanks
    2

    Re: Graph Theory

    Quote Originally Posted by Plato View Post
    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!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: March 30th 2012, 02:27 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum