My Math Forum Dirac theorem related excercise

 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 $P=\left(x_1,x_2,\ldots ,x_t\right)$ is a simple path of maximum longitude in a connected graph $G$ and if $x_1,x_t$ are adyacent, then $G$ is hamiltonian. Proof of Lemma: The cycle $C=\left(x_1,x_2,\ldots ,x_t,x_1\right)$ must go through all vertices. For if $y$ is not in $C$, let $L$ be the smallest path connecting $y$ with $C$ and let $x_i$ be the extreme of $L$ in $C$. The simple path $\left(y,L,x_i,x_{i+1},\ldots ,x_k,x_1,x_2,\ldots ,x_{i-1}\right)$ is longer than $P$. Proof of excercise: Let $C=\left(v_0,v_1,\ldots ,v_q\right)$ be a simple path of maximum longitude in $G$. If $v_0,v_q$ are adjacent, then $G$ is Hamiltonian and the theorem is trivially true. If $v_0,v_q$ are not adjacent, we have $\deg v_0+\deg v_q\geq k$. Since $C$ is maximal, it must contain every vertex adjacent with either of $]v_0,v_q$. If for every vertex $v_i$ adjacent to $v_0$ we have that $v_{i-1}$ is not adjacent to $v_q$, then $\deg v_q\leq q-\deg v_0$. Hence $k\leq \deg v_0+\deg v_q\leq q$ and the theorem holds. If not, let $v_{i-1},v_i$ be such that $v_0$ is adjacent with $v_i$ and $v_q$ is adjacent with $v_{i-1}$. The simple path $\left(v_0,v_1,\ldots ,v_{i-1},v_q,v_{q-1},\ldots ,v_i\right)$ has the same longitude as $C$ and hence is a simple path of maximum longitude in $G$. Moreover, its extremes are adyacent. By the lemma $G$ is Hamiltonian and the theorem holds.

 Tags dirac, excercise, related, theorem

 Thread Tools Display Modes Linear 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