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!

  • 1
    $\begingroup$ Do you mean a simple graph? $\endgroup$ – Tobias Kildetoft Sep 26 '17 at 9:04
  • $\begingroup$ @TobiasKildetoft yes, I mean a simple graph. $\endgroup$ – Ivon Sep 26 '17 at 9:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.