[Math] 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$.