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

The question is motivated by this and this two problems.

The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the same length.

The second problem shows that if $G$ has at least $n+4$ edges then it must contain two disjoint cycles.

My question now is

Question. What would be a lower bound for the number of edges in a graph that would force the graph to contain two disjoint cycles of same length?

By distinct cycles $C_1,C_2$ we mean that $E(C_1) \cap E(C_2) \ne E(C_1) \cup E(C_2)$ and we say that they are disjoint if $E(C_1) \cap E(C_2) = \emptyset$

share|cite|improve this question
A lower bound would be $\frac{n^2+6n+11}{4}$ which ensures that the graph has two disjoint cycles of length $3$: since $m > n^2/4$ the graph contains a triangle. Removing this triangle we get a graph with $n-3$ vertices and at least $\frac{n^2+6n+11}{4} - 3 - 3(n-3) > \frac{(n-3)^2}{4}$ edges hence this graph contains another triangle. I don't suspect this to be optimal though. – user133281 Mar 6 '14 at 11:51

To answer my own question, it appears that (see this paper) having $2n$ edges suffices.

share|cite|improve this answer

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.