Graph Path Length Problem

Question

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

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

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

Answer 1

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

Answer 2

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.