Number of edges in graphs having two disjoint cycles of equal length

739 Views Asked by At

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

There are 1 best solutions below

0
On

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