G is a graph on n vertices. Each vertex has degree at least 3, and G is not bipartite. Let k be the size of the smallest odd cycle in G. What is the largest k can be, as a function of n?

Vertices of degree 0 and 1 are clearly irrelevant. If we allowed vertices of degree 2 and n was odd, we could have G just be an n-cycle, and get k=n. So these cases kind of break down trivially. But when all degrees are at least 3, we can't have an n-cycle without having lots of chords. If the large cycle is odd and you start adding approximate diameters, you make a good construction until you've gone most of the way around, then you start getting small odd cycles again.

2more comments