Graph Path Length Problem

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

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.

a) Take a maximal path $P=v_0v_1 \ldots v_l$. As $P$ is maximal, all neighbourghs of $v_0$ are in $P$. As $v_0$ has at least $k$ neighbourghs, then $l \geq k$.