My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 20th, 2010, 07:25 PM   #1
Member
 
Joined: Apr 2010

Posts: 54
Thanks: 0

Dirac theorem related excercise

I need help with this excercise. Any ideas appreciated. Thanks.

Let G be a connected graph with n vertices and let k be a positive integer with k < n. Show that if for any two non-adjacent vertices x,y of G we have deg(x)+deg(y) >= k, then there is a simple path of longitude k in G.
becko is offline  
 
July 2nd, 2010, 10:26 AM   #2
Member
 
Joined: Apr 2010

Posts: 54
Thanks: 0

Re: Dirac theorem related excercise

I finally cracked this one. For whom it might interest:

Lemma:

If is a simple path of maximum longitude in a connected graph and if are adyacent, then is hamiltonian.

Proof of Lemma:

The cycle must go through all vertices. For if is not in , let be the smallest path connecting with and let be the extreme of in . The simple path is longer than .

Proof of excercise:

Let be a simple path of maximum longitude in .

If are adjacent, then is Hamiltonian and the theorem is trivially true.

If are not adjacent, we have .

Since is maximal, it must contain every vertex adjacent with either of .

If for every vertex adjacent to we have that is not adjacent to , then . Hence and the theorem holds.

If not, let be such that is adjacent with and is adjacent with . The simple path has the same longitude as and hence is a simple path of maximum longitude in . Moreover, its extremes are adyacent. By the lemma is Hamiltonian and the theorem holds.
becko is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
dirac, excercise, related, theorem



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question related to the Intermediate value theorem natt010 Real Analysis 12 December 30th, 2013 03:13 PM
De Moivre's Theorem Related - Complex number sachinrajsharma Algebra 1 March 20th, 2013 01:53 AM
Macroeconomics 3 - need help with an excercise Tilen Economics 0 November 7th, 2012 08:45 AM
Macroeconomics 3 - need help with an excercise Tilen Economics 0 November 7th, 2012 08:40 AM
A "simple" application of dirac delta "shift theorem"...help SedaKhold Calculus 0 February 13th, 2012 11:45 AM





Copyright © 2019 My Math Forum. All rights reserved.