Applied Math Applied Math Forum

 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. 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post natt010 Real Analysis 12 December 30th, 2013 03:13 PM sachinrajsharma Algebra 1 March 20th, 2013 01:53 AM Tilen Economics 0 November 7th, 2012 08:45 AM Tilen Economics 0 November 7th, 2012 08:40 AM SedaKhold Calculus 0 February 13th, 2012 11:45 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top      