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$

  • 1
    $\begingroup$ 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. $\endgroup$
    – user133281
    Mar 6 '14 at 11:51

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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