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 nonadjacent vertices x,y of G we have deg(x)+deg(y) >= k, then there is a simple path of longitude k in G. 
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. 

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 