# Is this theorem about girth and bipartite graph wrong?

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?

## 2 Answers

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.

• Thanks! It helps me a lot :) Commented Oct 6, 2018 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.

• Thanks. I got it! Commented Oct 6, 2018 at 19:48