Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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)$.

share|cite|improve this answer
What is an even Hamiltonian path? – Srivatsan Jul 31 '11 at 8:11
@Srivatsan As in, do we use vertices or edges? Is that your quetion? Surely, from the context, he is talking about the edges. And, since length of paths are usually defined in terms of edges, there doesn't seem to be any confusion. – Graphth Dec 12 '12 at 18:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.