Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be a graph such that $\delta(G) \geq k$.

a) Prove that $G$ has a path of length at least $k$.

solution: We know that $\delta(G) = \min\lbrace \deg(v) \mid v \in V(G) \rbrace$

if $\delta(G) = k$ then there exists some $v \in V(G)$ such that $\deg(v) = k$. This means all other vertices $u \in V(G)$ have $\deg(u) \geq k$.

Now I know this must be part of the proof. How would i prove that there exists a path of at least $k$?

b)if $k \geq 2$, prove that $G$ has a cycle of length at least $k+1$.

share|improve this question
3  
The title should be a precise 1-line summary of what your question is about, not the 1st sentence of the question. –  KennyTM Aug 11 '10 at 18:35
    
edited title due to comment –  gprime Aug 11 '10 at 18:56

2 Answers 2

up vote 2 down vote accepted

b) consider a path $v_0\dots v_k$ of length $k$ (existing for part a) and for Chandru's construction) such that $v_i \neq v_j$ $\forall i\neq j$.

  • If $v_0$ and $v_k$ are adjacent, you have a cycle of lenght $k+1$.
  • Otherwise, since $deg(v_k)\geq k$, $v_k$ has at least one adjacent vertex $v_l$ with $l>k$ and you can extend the path with this new vertex. If $v_l$ is adjacent with $v_0$ or $v_1$ you're done, otherwise you can extend the path again with a vertex that doesn't belong to the path yet. Since $G$ has only a finite number of vertices, at some point you will find a vertex $v_n$ whose adjacent vertices are all part of the path. $deg(v_n)\geq k$, so $v_n$ is adjacent to $v_i$ for some $i< n-k$ and you can finally close the path with a cycle of lenght $n-i \geq k+1$.
share|improve this answer
    
ok, i do get it now. Thanks a lot! –  gprime Aug 12 '10 at 18:21

You can construct path and cycle inductively. Start at an arbitrary vertex $v_0$, and move along an arbitrary edge to $v_1$. Since vertex $v_1$ has degree k or greater, it has at least $k-1$ neighbours other than $v_0$. Move along an edge to one of these neighbours $v_2$. Since vertex $v_2$ has degree $k$ or greater, it has at least $k-2$ neighbours other than $v_0$ and $v_1$. Move along an edge to one of these neighbours $v_3$. And so on... until you reach vertex $v_k$. At this stage, you already have a path of length $k$. There may then be no unvisited vertices left to move to, in which case v_0 must be one of them, and you can return to it for a cycle of length k+1. Otherwise, just keep on moving to new vertices. If when you get to vertex v_n you find that it is connected to one of the vertices $v_j$ for $0 \leq j \leq (n-k)$ then you can go back to that vertex for a cycle of length k+1 or greater. If not, then v_n will have a neighbour that you have not yet visited, and the journey can continue. Assuming that G has only finitely many vertices, you must eventually complete a cycle.

share|improve this answer
    
"There may then be no unvisited vertices left to move to, in which case v_0 must be one of them, and you can return to it for a cycle of length k+1." - how do you know that vk is adjacent to v0? –  gprime Aug 11 '10 at 20:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.