In this paper, the abstract mentions that the classical work of Andrásfai, Erdős, and Sós implies:

Every $n$-vertex graph with odd girth $2k+1$ and minimum degree bigger than $\dfrac{2}{2k+1}n$ must be bipartite.

I think the statement is wrong.

My idea is that if G is a graph with odd girth $2k+1$, then it contains an odd cycle (with length $2k+1$). Therefore G is not bipartite, which contradicts to the result of the statement.

Is that statement false? Or did I misunderstand something?


The result is not wrong. It's "saved" by the definition of odd girth: a graph's odd girth is at least $g$ if it contains no odd cycles of length less than $g$. In effect, the classical work showed that graphs with the stipulated minimum degree and lower bound on the odd girth must in fact have no odd cycles at all and therefore be bipartite.

  • $\begingroup$ Thanks! It helps me a lot :) $\endgroup$ – Jerry Chang Oct 6 '18 at 19:41

If you look about the middle of page 2, they define "a graph has odd girth at least $g$ if it contains no odd-length cycle of length less than $g$".

In other words they use a concept called "odd girth" which is not the same as saying the girth is odd.

I agree it looks quite confusing though.

  • $\begingroup$ Thanks. I got it! $\endgroup$ – Jerry Chang Oct 6 '18 at 19:48

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.