Length of odd cycle in a non-bipartite simple graph

Question

---

Update: solved!

Let $G$ be a non-bipartite simple graph with its minimum degree $\delta > [2V/(2k+1)]$, where $V$ denotes the number of vertices of $G$, and $k>=2$ is an integer. Show that $G$ has odd cycles of length $<=2k-1$.

---

I do not know how to deal with this problem, but I have thought about the simplest situation when $k=2$. Then the extreme situation is something like nested pentagon-cycles, where each vertex of the graph has edges exactly with vertices from different vertex of pentagon. Then the graph is non-bipartite and satisfies all the conditions. And in this graph it is clear that $G$ has triangles. Please help with the general situation. thank you!

Answer 1

Suppose $G$ does not have an odd cycle of length $<2k-1$. Then taking its shortest odd cycle $S$ we get $length(S)=|V(S)|>=2k+1$. Denote by $S^c$ the complement of $S$. Then counting the number of edges between these 2 parts we have $|(S, S^c)|=\sum_{i \in S} {(d_i-2)}$, where $d$ is the degree of the vertex. Meanwhile, we claim that $|(S, S^c)|<=2(V-|V(S)|)$. In fact otherwise there is some vertex $u$ in $S^c$ such that 3 vertices $x$, $y$, $z$ in $S$ have edges with it. Then since $G$ does not contain triangle, there exist $a$, $b$, $c$ between $yz$, $zx$, $xy$ in $S$, respectively. Thus consider 3 cycles $uyazu$, $uzbxu$, $uxcyu$, we get at least one odd cycle shorter than $S$. Contradiction! So the claim is correct. Then we get $\sum_{i \in S} {(d_i-2)} <= 2(V-|V(S)|)$, and this leads to $\delta <=2V/|V(S)| <= 2V/(2k+1)$. A contradiction! The proof completes.