Smallest odd cycle in a non-bipartite graph

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.

• The shortest odd cycle in the Cartesian product of $C_k$ and $K_2$ for odd $k$ contains half of the vertices, not sure if that's best possible though. Apr 10, 2019 at 19:48
• I'm not sure how to prove it either, but that sounds probably tight. For n=4m+2 that gives at least 2m+1=n/2. For other values of n mod 4, I'm now thinking any ways to add a vertex or two to that construction. For n=4m+3, 4m+4 or 4m+5 I see how to still get k≥2m+1 (with modifications not worth describing in a comment) but I'm much less confident those would be tight. Apr 10, 2019 at 20:03
• To add a vertex, just make a copy of an existing one Apr 10, 2019 at 21:32
• "In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an $(r,g)$-graph is defined to be a graph in which each vertex has exactly $r$ neighbors, and in which the shortest cycle has length exactly $g$." (quoting Wikipedia). So maybe you want to check out the literature on "cage graphs". Apr 10, 2019 at 22:01
• @GerryMyerson I appreciate the recommendation, but cage graphs also avoid small even cycles. I did search for "odd cages" or something, but without success. Apr 10, 2019 at 22:07

I care only about linear term in the answer, relaxing an additive constant. However, for $$n=12k+11$$ I show the tight answer.
An example I told in a comment was slightly suboptimal. An optimal one is the following. Take a cycle of length $$8k+7$$, number its vertices from 1 to $$8k+7$$, and duplicate those with residues $$2,3,6,7$$ modulo 8. We get $$n=12k+11$$ vertices, so a shortest odd cycle has length of almost $$2n/3$$. See below an example for $$k=0$$.
Assume a shortest odd cycle has length more than $$2n/3$$. The cycle has no chords (otherwise we shorten the cycle), so each its vertex has a neighbor outside the cycle. Then three vertices have the same outer neighbor, which again leads easily to shortening the cycle (if $$n$$ is large).
Notice that exactly $$2n/3$$ is also impossible, as this number is even whenever integer.