Let $G$ be a simple graph G such that every vertex has degree at least $k\geq 3$ and every cycle of $G$ has length at least $5$. Show that $G$ contains a cycle of length at least $3k$.
Let $P$ be a path of maximum length. By contradiction, assume that the longest cycle has length at most $3k − 1$. I want to show that $G$ has a cycle of length $4$. I tried to mimic the method in Diestel Proposition 1.3.1 to get the proof, but it didn't work.
Any hint would be highly appreciated.
Best Answer
As saulspatz commented, you can use Diestel $1.3.1$ and immediately obtain a cycle of length $3k-1$. But here's how to get $3k$. I talked this out with someone, and we may have arrived at a proof.
Let $P$ be a maximum path in $G$, let $v$ be an endpoint of $P$, and let $u$ be the vertex adjacent to $v$ previously on the path. Since $\deg(v) \ge 3$, $v$ has at least $2$ additional vertices on the path. Since a cycle in $G$ has length at least $5$, the first neighbor of $v$ must be at least $4$ edges away from $v$ on $P$, and every subsequent neighbor must be at least $3$ edges apart from the other neighbors (Otherwise we'd get a cycle of length $4$ or $3$.) So let's pick our neighbors in a minimum fashion, that is, in a way that we are not guaranteed a cycle of length $3k$ immediately.
So far we've got the existence of a cycle of length $3k-1$, but maybe we can increase the length of this cycle. Let's consider $2$ cases in the following way.
Since $\delta(G) \ge 3$, $u$ has at least $1$ more neighbor, $u'$.
Case $1$: $u'$ is not on $P$.
We can think of $u'$ as the endpoint of $P$, and $u'$ must have a neighbor further down the path than all the neighbors of $v$ (otherwise we obtain a cycle of length less than $5$), extending our cycle of length $3k-1$ to $3k$. (This uses the fact that $\deg(u')\ge 3$ and the neighbors of $u'$ lie on $P$).
Case $2$: All of the neighbors of $u$ are on $P$.
Notice $u$ cannot have any neighbors that are adjacent to a neighbor of $v$, otherwise we get a cycle of length less than $5$. So $u$ has a neighbor $u'$ farther on $P$ than the farthest neighbor $v'$ of $v$, and so our cycle is $u \to u' \to v' \to v \to u$, which has length greater than $3k-1$.