# What is the maximum length of shortest odd cycle in a non-bipartite graph?

Let $G = (V, E)$ be a connected, undirected, and non-bipartite graph. What is the maximum length of the shortest odd cycle?

I'm working on an algorithm for computing bipartivity degree. See, for example, section 7.2 of Characterization of Complex Networks: A Survey of measurements. My algorithm is similar in some ways to subgraph centrality, but it's not a spectral algorithm; that is, it's not expressed in terms of the eigenvalues or eigenvectors of the adjacency matrix of the graph. Instead, I find certain kinds of closed walks of length $1 \ldots k$. So, if there's an known upper bound on the length of the shortest odd cycle in a non-bipartite graph, then I can know how large $k$ must be in order to capture some information about how far from being bipartite a non-bipartite graph is.

-
Take a cycle, $C_{2n+1}$. –  Aryabhata Apr 25 '11 at 4:20

This problem might be NP-Hard, since it's similar to finding the longest even Hamiltonian path, $p = (v \rightarrow w)$ , in $G$ s.t. $e = (v,w) \in E(G)$.