Prove G has path of length >= k and cycle of length....

[hero]

Let G be a graph in which every vertex has degree at least k, where k is an integer at least 2. Prove that G has a path of length at least k and a cycle of length at least k+1.

graph theory keeps confusing me. please help. thank you.

 

[Opalg]

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 $\displaystyle 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.