Given any positive real number $\varepsilon$, prove that, for all but finitely many positive integers $v$, any graph on $v$ vertices with at least $(1+\varepsilon)v$ edges has two distinct simple cycles of equal lengths. (Recall that the notion of a simple cycle does not allow repetition of vertices in a cycle.) Fedor Petrov, Russia
Problem
Source: RMM 2019
Tags: RMM, RMM 2019, combinatorics, graph theory, cycles, Fedya, probability
23.02.2019 13:45
See this then xDDDD
23.02.2019 15:12
The main idea of almost every solution is to think of the spanning forest(collections of the spanning tree of each component). There are less than $v$ edges in the spanning forest. What happened while we removed the $\varepsilon v$ edges? Also, we should use that if we have $k$ distinct simple cycles, the sum of the lengths should be more than $1+2+\cdots +k=\frac{k(k-1)}{2}$.
23.02.2019 15:35
For each $n$, denote by $f(n)$ the smallest $m$ such that any simple graph with at least $m$ edges has two simple cycles of the same length. Then the problem asks to prove the asymptotic equivalence $f(n) \sim n$ (since clearly $f(n) \geq n$ for all $n$). We will prove that in fact $f(n) = n + O(n^{\frac{3}{4}})$. First, we can WLOG assume that the graph is connected. Indeed, if it consists of $c$ components, we can add $c - 1$ edges to make it connected. In this way the new graph has the same cycles as the starting one since none of the added edges can be part of a cycle. Suppose no two cycles in the graph $G$ have the same length. Consider a DFS tree $T$ of $G$. It is a rooted spanning tree with the property that each edge of $G$ not in $T$ (called a back edge) connects a vertex with its ancestor in $T$. It can be constructed by running the DFS algorithm starting from an arbitrary vertex. So let $(u_1, v_1), \ldots, (u_k, v_k)$ be the back edges, where $v_i$ is an ancestor of $u_i$ for all $i$. Also let $l_i$ be the length of the path from $u_i$ to $v_i$ in $T$. Claim: $\sum_{i = 1}^{k} l_i \geq \frac{k(k + 1)}{2}$ Proof: Note that the path from $u_i$ to $v_i$ in $T$ and $(u_i, v_i)$ form a simple cycle $C_i$ of length $l_i + 1$ in $G$. Since the $C_i$ are pairwise distinct, it follows that the $l_i$ are pairwise distinct, so the claim follows. $\square$ Now for each vertex $a$ in $G$, let $B_a$ be the set of back edges $(u_i, v_i)$ that "jump over" $a$, i.e. such that $u_i$ is in the subtree of $a$ and $v_i$ is not. Claim: For all $a$ in $G$ we have ${{|B_a|}\choose{2}} \leq n.$ Proof: Since each simple cycle in $G$ has length at most $n$, we have at most $n$ cycles in total. So it suffices to exhibit an injection from the set of pairs of elements of $B_a$ to the set of simple cycles in $G$. To do this, note that if $(u_i, v_i), (u_j, v_j) \in B_a$ are distinct, we can map this pair to the simple cycle consisting of $(u_i, v_i)$, the path in $T$ from $v_i$ to $v_j$, $(u_j, v_j)$ and the path in $T$ from $u_j$ to $u_i$ in that order. $\square$ Claim: $\sum_{a \in G}^{} |B_a| = \sum_{i = 1}^{k} l_i$ Proof: This follows immediately by double counting the pairs $(a, e)$, where $e$ is a back edge that jumps over $a$. $\square$ Finally, by the first and third claim, there exists $a \in G$ such that $|B_a| \geq \frac{k(k + 1)}{2n}$. Hence, the second claim implies that $k = O(n^{\frac{3}{4}})$, so $G$ has $n - 1 + k = n + O(n^{\frac{3}{4}})$ edges, as desired.
23.02.2019 18:48
In fact you can get $O(\sqrt{n})$ with an algorithm.
23.02.2019 19:03
Here is a very different solution than the above. Let $G$ be an arbitrary simple graph with edges $e_1,e_2, \dots, e_{E}$. Interpret cycles as vectors in $\mathbb F_2^{E}$ where cycle $c$ has a $1$ in the $i$th position iff it contains edge $e_i$. Lemma: We can find at least $E-V+1$ linearly independent cycles. Proof: Induct on $E-V+1$ with base case $E-V+1=1$ trivial (as this implies $E=V$, so obviously a cycle exists). For the inductive step, take an arbitrary edge $e_1$ belonging to some cycle $c_1$ and remove it from the graph. By the inductive hypothesis we can find linearly independent cycles $c_2, c_3, \dots, c_{E-V+1}$, and it's clear we can add $c_1$ to this collection. Now let $k = \epsilon v$ and suppose we found $k$ linearly independent cycles $c_1,c_2, \dots, c_k$ from the lemma. Also suppose that graph $G$ has cycles of length $a_1,a_2,\dots, a_m$ (here we look at all cycles of the graph, not just the $k$ we found earlier). For any $S\subseteq \{1,2,\dots, k\}$, it's clear that $\sum_{s\in S} c_s$ (where addition is modulo $2$) decomposes into the union of some edge-disjoint cycles. This means each $\sum_{s\in S}c_s$ corresponds to some subset $T\subseteq \{1,2,\dots, m\}$ of the cycles in the graph such that $\sum_{t\in T} a_t \le E = (1+\epsilon )V$. Since the $c_i$ are linearly independent, all $2^k$ possible $\sum_{s\in S}c_s$ terms are distinct, so we get at least $2^k$ distinct subsets $T\subseteq \{1,2,\dots, m\}$ such that $\sum_{t\in T} a_t \le (1+\epsilon)V$. Assuming for contradiction the $a_i$ are pairwise distinct, it follows that $\sum_{t\in T} a_t \ge 2+3+\dots + (|T|+1)$, so therefore $|T| \le \sqrt{2(1+\epsilon) V}$. Then the total number of $T$ is at most $\binom{m}{0}+\binom{m}{1}+\dots + \binom{m}{\sqrt{2(1+\epsilon ) V}}$. This is at most $\sqrt{2 (1+\epsilon) V} m^{\sqrt{2(1+\epsilon) V}}$. If $V$ is sufficiently large and $m<V$, then this final expression will clearly be less than $2^k = 2^{\epsilon V}$, contradiction. Therefore for all large $V$ we have $m\ge V$, so by Pigeonhole two of the $m$ cycles have equal length, and we're done. Note this solution also works for $E=V+O(\sqrt{V}\log V)$.
23.02.2019 20:03
We can show that the number of edges is at most $n+2\sqrt{n}+1$ with the probabilistic method and alteration. Suppose a graph $G$ has $E$ edges and no repeated cycle lengths. Then I claim that there exists a subset $A$ of at most $2\sqrt{E}$ edges that intersects every cycle. If we pick an arbitrary subset $B$ of the edges, and let $f(B)$ be the number of cycles which do not intersect $B$, then we can achieve a set of $|B|+f(B)$ edges which intersects all cycles. Let $B$ be chosen randomly with every edge independently in the set with probability $\frac{1}{\sqrt{E}}$. Then $\mathbb{E}[|B|+f(B)]=\mathbb{E}[|B|]+\mathbb{E}[f(B)]$. The expected size of $B$ is just $\sqrt{E}$, and the expected value of $f(B)$ is the sum over all cycles of the probability of that cycle not containing any element from $B$. This probability is just $(1-\frac{1}{\sqrt{E}})^k$ for a cycle of length $k$. The key fact is then that no cycle length is repeated, so $\mathbb{E}[f(B)]\le \sum_{k=3}^\infty (1-\frac{1}{\sqrt{E}})^k$ which is at most $\sqrt{E}$ by geometric series, giving the desired result. If we remove this set of edges, we break all cycles and thus the remaining graph has at most $n-1$ edges, so the original graph had at most $n-1+2\sqrt{E}$ edges, implying $E\le n-1+2\sqrt{E}$ which implies the desired inequality.
23.02.2019 20:19
Very nice solutions with $n+C\sqrt{n}$, both greedy and probabilistic! Actually I did not get such a sharp estimate while thinking on the question.
23.02.2019 21:01
Perhaps a little uglier - easy to see it suffices to consider the case where the graph is connected, as if we prove that case for $.1\epsilon$ then we can assume for $\epsilon$ that all components are either small (size $O_{\epsilon}(1)$) or sparse (average degree $<2+.1\epsilon$). Then there can only be constantly ($O_{\epsilon}(1)$) components that are not sparse, before there are too many small components with a cycle and a cycle length is repeated. But then the graph is a disjoint union of something of size $O_{\epsilon}(1)$ and something whose average degree is $<2+.1\epsilon$, which is impossible unless the graph itself is size $O_{\epsilon}(1)$. Now if the graph is connected take a spanning tree $T$. Now look at every cycle in $G$ of length at most $.1\epsilon n$ and remove an edge from it which is not in $T$, removing at most $.1\epsilon$ edges. The remaining graph $G'$ has $E(G')=E(T) \cup E'$ for some set $E'$. Start with $T$ and put the edges of length $E'$ onto it one by one. Call two vertices close if their distance is at most $.01\epsilon n$. Every time an edge from $E'$ is added, it connects two vertices $(a,b)$ of distance at least $.1\epsilon$, so it makes at least $\Omega_{\epsilon}(n^2)$ pairs of vertices close that were not close before, in particular every pair of vertices $(x,y)$ so that $x$ is within $.001\epsilon$ of $a$ and $y$ within $.001\epsilon$ of $b$. Thus $|E'|=O_{\epsilon}(1)$, a contradiction as $|E'|=\Omega_{\epsilon}(n)$. Remark: I believe this argument proves it for a connected graph with $n+100n^{2/3}$ edges, so not quite the optimal $\sqrt{n}$. Call two vertices close if they are within distance $4n^{2/3}$. We can remove an edge from every cycle of length at most $10n^{2/3}$ and then add $90n^{2/3}$ edges in to a spanning tree, each one connecting two vertices of distance at least $10n^{2/3}$ and thus making $4n^{4/3}$ pairs of vertices close that were not close before. But there are not $360n^2$ pairs of vertices in the graph, a contradiction. But this is tight only by a constant factor. So this can't do better than $n+Cn^{2/3}$ edges for some constant $C$. Unfortunately the first paragraph appears to require a constant $\epsilon$ though.
23.02.2019 21:10
23.02.2019 22:27
Here is a solution using standard tools from the algorithmic graph theory literature. For more on related problems and techniques, you can look at this. Lemma 1 (low diameter decomposition): In a graph $G$ with $n$ vertices and $m$ edges, you can delete $\delta m$ edges so that all resulting connected components in the remaining graph have diameter $O(\delta^{-1} \log n).$ Proof: Run the following algorithm. Start at a vertex $v$, and define $B_r$ to be the set of all vertices within distance $r$ of $v$. Find the minimal $r$ with $E(B_r) \le (1+\delta)E(B_{r-1})$, and make $B_{r-1}$ one of your final connected components / delete that subset of vertices from the graph. Clearly, we have deleted at most $\delta m$ edges as the number of deleted edges is at most \[ \sum (E(B_r) - E(B_{r-1})) \le \sum \delta \cdot E(B_{r-1}) \le \delta m. \]Also, the condition we desired holds for some $r = O(\delta^{-1} \log n)$ as desired. Now use the Lemma with the parameter $\delta = \frac{\varepsilon}{2}.$ Build a spanning tree of depth $O(\varepsilon^{-1} \log n)$ on each of the remaining connected components. Now, we have at least $\frac{\varepsilon}{3}n$ edges that haven't been deleted and are not in any spanning tree. Each of these now obviously creates a cycle of length $O(\varepsilon^{-1} \log n)$ (just use the edges in spanning trees). Now, we just need $\frac{\varepsilon}{3}n \le O(\varepsilon^{-1} \log n)$ which holds for $\varepsilon = O(\sqrt{n \log n}).$ Therefore, this approach gives a bound of $n + O(\sqrt{n \log n})$.
23.02.2019 23:51
Here's a construction for $n+\sqrt{2n}$ (so you can't prove anything stronger than $n+O(\sqrt{n})$). Consider cycles of lengths $3,4,5,\cdots,k$, then join them together by their vertices in a chain. (The resulting graph has $1+2+3+4+5+\cdots+(k-1)$ vertices and $3+4+5+\cdots+k$ edges.)
28.02.2019 12:10
Consider a spanning tree $T$ in the graph. We then add $\epsilon n$ new edges. Let the degree $D(E_i)$ of a new edge $E_i=\overline{v_iu_i}$ be the length of the path $P(v_i,u_i)$ between $v_i$ and $u_i$ along $T$. Each $E_i$ forms a new cycle of length $D(E_i)+1$ with the spanning tree $T$. Since the cycle lengths are distinct, this means that $D(E_i)$ is also distinct. The key idea is that two new edges $E_i$, $E_j$ can sometimes also form a cycle. If $P(v_i,u_i)$ and $P(v_j,u_j)$ intersect at $\overline{vu}$, then they will form a new cycle (in red) $\overline{v_ivv_ju_juu_i}$ as shown [asy][asy] pair A,B,C,X,Y,Z; A = (0,0); label("$v_j$",(0,0),S); B = (2,1); label("$v$",(2,1),S); C = (0,2); label("$v_i$",(0,2),S); X = (5,0); label("$u_j$",(5,0),S); Y = (3,1); label("$u$",(3,1),S); Z = (5,2); label("$u_i$",(5,2),S); draw(A--X, red+dotted); draw(C--Z, red+dotted); draw(A--B,red); draw(C--B,red); draw(X--Y,red); draw(Y--Z,red); draw(B--Y,black); dot(A); dot(B); dot(C); dot(X); dot(Y); dot(Z); [/asy][/asy] For each good edge $E_i$, color $P(v_i,u_i)$ in color $i$. Let each edge $F_i$ in the spanning tree be colored in $C(F_i)$ colors. Then, $$ \sum_i C(F_i) \ge \sum_i D(E_i)\ge 1+2+\cdots +\epsilon n \ge c_1n^2$$By Jensen's inequality, $$ \#(color 1, color 2, F_i) = \sum_i {C(F_i) \choose 2} \ge n {c_1 n \choose 2} \ge c_2 n^{3}$$Every two paths intersect at at most $n$ edges of the spanning tree. Hence, $$ \#(color 1, color 2) \ge \frac{c_2 n^{3}}{n}\ge c_2n^{2}$$Hence, there are at least $c_2n^{2}$ pairs of $E_i, E_j$ that form new cycles, which leads to a contradiction.
02.07.2019 11:42
Here is a very unique solution I found while we are doing this as the Mock IMO. Unfortunately, this gets only $n+o(n)$ bound. Take a large positive integer $k$ such that $\varepsilon(1+\varepsilon)^k > 2019$. Consider a graph $G$ with $v$ vertices, at least $(1+\varepsilon)v$ edges and distinct cycles lengths. The first idea is to remove all edges of cycle of length $3,4,5,...,k$. We loses at most $k^2$ edges. Let the new graph $G$ has $e > (1+\varepsilon)v - k^2$ edges. Now, the key idea is consider any $v$-edges subgraph of $G$. There are $\tbinom{e}{v}$ such subgraphs, each having at least one cycle. However, a cycle of length $i$ is contained in at most $\tbinom{e-i}{v-i}$ such subgraphs. As there are at most one cycle each length $k+1,k+2,...,v$, this means $$\binom{e}{v}\leqslant\binom{e-k-1}{v-k-1} + \binom{e-k-2}{v-k-2} + \hdots + \binom{e-v}{v-v}$$By Hockey Stick identity, this reduces to $$\binom{e}{v}\leqslant\binom{e-k}{v-k-1} \iff \frac{e(e-1)(e-2)...(e-k+1)(e-v)}{v(v-1)(v-2)...(v-k)}\leqslant 1$$Taking $v$ large enough, we find that the numerator is $\gg\varepsilon(1+\varepsilon)^k v^{k+1} \gg 2019v^{k+1}$ while the denominator is clearly $\sim v^{k+1}$. This is a contradiction for all sufficiently large $v$.
07.07.2019 16:55
We prove any graph with $n$ vertices and $n+O(n^{3/4})$ edges does the job. The approach uses a spanning tree (of special kind) and then estimates the number of cycles using the Turan theorem (of cliques). Let $T$ be the spanning tree of the given graph $G$, obtained by depth first search algorithm. So, the edges in $E':=E(G)\setminus E(T)$ are not cross edges of $T$. Let $e=v_1v_2\in E'$, thus $v_1$ and $v_2$ are compatible with respect to $T$ and suppose $v_1<v_2$. For any such $e\in E'$ we map $e$ to the path $p(e)$ in $T$ connecting $v_1$ with $v_2$. Arguing by contradiction, suppose all cycles in $G$ are of distinct lengths. Since $v_1 p(e)v_2v_1$ is a cycle, for each $e\in E'$ , it follows all paths $p(e),e\in E'$ have distinct lengths. Claim: For any set of $2\sqrt{n}$ paths $p(e),e\in E'$ , there are two of them which intersect each other. Indeed, since their lengths are all distinct, their total length is at least $\sqrt n (2\sqrt n +1)>n-1$ , which means some two of them intersect, since the total length of all edges in the tree $T$ is $n-1$. $\blacksquare$ The plan is to estimate via this claim a lower bound of $m=|E'|$ using the Turan theorem. We can treat the objects $p(e), e\in E'$ as being vertices of a new graph $P$. Two vertices (paths) in $P$ are connected iff the corresponding paths have non empty intersection. The above claim says there doesn't exist a $2\sqrt{n}$-clique in the complement $\overline{P}$ of $P$. By the Turan theorem the number of edges in $\overline{P}$ are at most $\displaystyle \left(1-\frac{1}{2\sqrt{n}-1} \right)\frac{m^2}{2}$. It implies the edges in $P$ are at least $$\displaystyle \frac{m(m-1)}{2}-\left(1-\frac{1}{2\sqrt{n}-1} \right)\frac{m^2}{2}>\frac{m^2}{8\sqrt{n}}.$$Now, taking $m=\left\lceil 2\sqrt 2 n^{3/4}\right \rceil$ we obtain the number of cycles in the original graph are at least $\frac{m^2}{8\sqrt{n}}>n$, which is a contradiction since they are of distinct lengths. In other words, any graph $G$ of $n$ vertices and $n+O(n^{3/4})$ edges has two cycles of equal lengths. Remark: It's the same approach I've used in this Iran 3-rd round 2013 problem, but optimized at the end with an application of the Turan theorem. In fact, the OP corresponds to a problem of Erdos about the maximum number of edges in a graph with $n$ vertices without two cycles of equal length.
01.02.2020 12:36
Finally I'm able to solve this on my own WLOG assume that the graph is connected, and all cycles have different length. Consider a DFS tree $T$ of the graph. Since the graph is simple, the other $\varepsilon v$ edges are all back-edges. We will find bounds of the number of cycles. Since all cycles are of distinct length, we have a linear upper bound on $v$. Now we will give a lower bound of $O(v^{\frac{3}{2}})$, thus leading a contradiction for sufficiently large $v$. Let us first fix a back-edge $e$. By adding $v$ on $T$, we obtain a unique cycle determined by $e$ and some edges of $T$. This gives exactly $\varepsilon v$ distinct cycles, but this is not enough. Now we seek to find cycles with exactly two back edges. Let $e_1= ab, e_2=cd$ be back edges. If the unique path $a \rightarrow b $ and $c \rightarrow d$ on $T$ aren't edge-disjoint, then there is a cycle containing edges of $T$ and $e_1, e_2$. Let us call such pair $\{ e_1, e_2 \}$ nice. Let $H$ be a graph on $\varepsilon v$ vertices, each representing a back-edge, and draw edges corresponding to nice pairs. For a back-edge $e=xy$, call the unique path $x \rightarrow y$ on $T$ the tree-path of $e$. If $A \subseteq V(H)$ is independent, then the tree-path of $a \in A$ are all disjoint, and since its length are all distinct, $v-1 \ge 2+3+\cdots + |A| \ge \frac{|A|^2}{2}$, or $|A| \le 2\sqrt{v}$. Now consider a maximal independent set $I_0$ of $H$. Then, by the maximality, there are at least $\varepsilon v-|I_0| \ge \varepsilon v -2\sqrt{v}$ edges between $I_0$ and $H-I_0$. Similarly, let $I_1$ be the maximal independent set of $H-I_0$, and define $I_2, \cdots, I_{\varepsilon\sqrt{v}/2}$ similarly. Then we have at least $$\varepsilon v-2\sqrt{v}+\varepsilon v -4 \sqrt{v}+\cdots +\varepsilon v-\left(\frac{\varepsilon \sqrt{v} }{2} \right) \cdot 2\sqrt v \sim \frac{\varepsilon^2v^{3/2}}{2} - \frac{\varepsilon^2v^{3/2}}{4}=O(v^{3/2})$$edges, which corresponds to distinct cycles of the original graph. Hence we are done. $\blacksquare$
03.02.2020 23:48
lminsl wrote: ... Now we will give a lower bound of $o(v^{\frac{3}{2}})$, thus leading a contradiction for sufficiently large $v$. ... Then we have at least $$\varepsilon v-2\sqrt{v}+\varepsilon v -4 \sqrt{v}+\cdots +\varepsilon v-\left(\frac{\varepsilon \sqrt{v} }{2} \right) \cdot 2\sqrt v \sim \frac{\varepsilon^2v^{3/2}}{2} - \frac{\varepsilon^2v^{3/2}}{4}=o(v^{3/2})$$edges, which corresponds to distinct cycles of the original graph. Hence we are done. $\blacksquare$ Never ,ever $o(\cdot)$ can be a lower bound. By definition it's an upper bound. I didn't read the solution, but anyway, having at least $\frac{\varepsilon^2v^{3/2}}{4}$ distinct cycles doesn't mean anything! That quantity may be even less than $1$.
03.02.2020 23:55
dgrozev wrote: lminsl wrote: ... Now we will give a lower bound of $o(v^{\frac{3}{2}})$, thus leading a contradiction for sufficiently large $v$. ... Then we have at least $$\varepsilon v-2\sqrt{v}+\varepsilon v -4 \sqrt{v}+\cdots +\varepsilon v-\left(\frac{\varepsilon \sqrt{v} }{2} \right) \cdot 2\sqrt v \sim \frac{\varepsilon^2v^{3/2}}{2} - \frac{\varepsilon^2v^{3/2}}{4}=o(v^{3/2})$$edges, which corresponds to distinct cycles of the original graph. Hence we are done. $\blacksquare$ Never ,ever $o(\cdot)$ can be a lower bound. By definition it's an upper bound. I didn't read the solution, but anyway, having at least $\frac{\varepsilon^2v^{3/2}}{4}$ distinct cycles doesn't mean anything! That quantity may be even less than $1$. Suppose Iminsl meant $O$ instead $o$. Isn't it true that showing there are at least $\varepsilon^2 v^{3/2}/4$ cycles enough? Because eventually this will be bigger than $(1+\varepsilon)v$, at which point there must be two cycles of same length?
04.02.2020 10:54
Ok, $O(\cdot)$ is also used only for an upper bound! By definition. But the problem is not with the notations. lminsl wrote: ... Now consider a maximal independent set $I_0$ of $H$. Then, by the maximality, there are at least $\varepsilon v-|I_0| \ge \varepsilon v -2\sqrt{v}$ edges between $I_0$ and $H-I_0$. Similarly, let $I_1$ be the maximal independent set of $H-I_0$, and define $I_2, \cdots, I_{\varepsilon\sqrt{v}/2}$ similarly. Then we have at least $$\varepsilon v-2\sqrt{v}+\varepsilon v -4 \sqrt{v}+\cdots +\varepsilon v-\left(\frac{\varepsilon \sqrt{v} }{2} \right) \cdot 2\sqrt v \sim \frac{\varepsilon^2v^{3/2}}{2} - \frac{\varepsilon^2v^{3/2}}{4}$$edges, which corresponds to distinct cycles of the original graph. Hence we are done. $\blacksquare$ I didn't get it. For example each time the maximal independent set may consist of only one element (whu not?). So, what is the contradiction in this case?
04.02.2020 15:41
dgrozev wrote: I didn't get it. For example each time the maximal independent set may consist of only one element (whu not?). So, what is the contradiction in this case? The idea goes like this: Take any maximal independent set $I_0$ of $H$. Then $|I_0| \le 2\sqrt{v}$ by the above discussion. Also, by the "maximal independent set" condition, every vertex in $H-I_0$ is adjacent with some vertex of $I_0$. Hence there are at least $|H-I_0|=\varepsilon v - |I_0| \ge \varepsilon v - 2\sqrt{v}$ edges between $I_0$ and $H-I_0$. Now consider the induced subgraph of $H-I_0$. Let $I_1$ be the maximum independent set there. Then similarly $|I_1| \le 2\sqrt{v}$, and there are at least $|H-I_0-I_1| =\varepsilon v -|I_0|-|I_1| \ge \varepsilon v -4\sqrt{v}$ edges between $I_1$ and $H-I_0-I_1$. Proceed these steps $\varepsilon \sqrt{v}/2$ times(nearly when you run out of vertices), then since these edges are all distinct, you'll get a lower bound on the number of edges of $H$. However, by the definition of $H$, these edges corresponds to distinct cycles of the original graph. Hence we have found $O(v^{3/2})$ cycles on the original graph, whereas there are only $v-2$ possible cycle lengths. This is clearly impossible for large $v$, thus we can find distinct cycles with same length if $v$ is sufficiently large. Hence, for example, if the maximal independent set is of size $1$, then we have lots of vertices outside of it, thus giving lots of edges.
04.02.2020 16:47
lminsl wrote: ... Now consider the induced subgraph of $H-I_0$. Let $I_1$ be the maximum independent set there. Then similarly $|I_1| \le 2\sqrt{v}$, and there are at least $|H-I_0-I_1| =\varepsilon v -|I_0|-|I_1| \ge \varepsilon v -4\sqrt{v}$ edges between $I_1$ and $H-I_0-I_1$. ...Proceed these steps $\varepsilon \sqrt{v}/2$ times(nearly when you run out of vertices), then since these edges are all distinct, you'll get a lower bound on the number of edges of $H$. What does "between" means. It may not be "vertex to vertex", e.g. one tree path may contain the other entirely. So, in that case, it may happen an edge "between " $I_0$ and $H-I_0$ to be also between $I_1$ and $ H-I_0-I_1$, that's they may not be distinct edges? Have you thought about that?
04.02.2020 16:51
dgrozev wrote: What does "between" means. It may not be "vertex to vertex", e.g. one tree path may contain the other entirely. By "between", I meant an edge of $H$ having one endpoint in $I_1$ and the other one in $H-I_0-I_1$. dgrozev wrote: So, in that case, it may happen an edge "between " $I_0$ and $H-I_0$ to be also between $I_1$ and $ H-I_0-I_1$, that's they may not be distinct edges? Have you thought about that? Could you explain precisely? $H$ is the graph having its vertex set as the $\varepsilon v$ edges that we deleted on the original graph; it is not the original graph itself.
04.02.2020 20:20
See the attached image. I put a vertical space between edges, but actually they are on the same path. So, your tree is a path and you have $4$ back edges. $H_0$ is a maximal "independent" set. You count edge $e$ once. Remove $H_0$, and take $H_1$. The edge $e$ is counted for the second time and so on. You see, $e$ is counted on the every step! Thus, some (actually, many) of those $\sim v^{3/2}$ edges are counted more than once!
05.02.2020 06:13
dgrozev wrote: See the attached image. I put a vertical space between edges, but actually they are on the same path. So, your tree is a path and you have $4$ back edges. $H_0$ is a maximal "independent" set. You count edge $e$ once. Remove $H_0$, and take $H_1$. The edge $e$ is counted for the second time and so on. You see, $e$ is counted on the every step! Thus, some (actually, many) of those $\sim v^{3/2}$ edges are counted more than once! No, we're not counting the edges of the original graph. Let me clarify that part: lminsl wrote: Now we seek to find cycles with exactly two back edges. Let $e_1= ab, e_2=cd$ be back edges. If the unique path $a \rightarrow b $ and $c \rightarrow d$ on $T$ aren't edge-disjoint, then there is a cycle containing edges of $T$ and $e_1, e_2$. Let us call such pair $\{ e_1, e_2 \}$ nice. Let $H$ be a graph on $\varepsilon v$ vertices, each representing a back-edge, and draw edges (on $H$) corresponding to nice pairs. We're finding the number of nice pairs of the original graph, which are represented as edges of the graph $H$. Hence, as in your example, we're not counting $e$, we're counting the pair $(e, H_0)$. Thus, in your example, we first count the "nice pairs" $(H_0, e)$, $(H_0, H_1)$, $(H_0, H_2)$, and delete $H_0$ on $H$, and then $H_1$ becomes the maximum independent set, hence we then count the "nice pairs" $(H_1, e)$ and $(H_1, H_2)$. Then we delete $H_1$. Then $H_2$ is the maximum independent set, hence we count $(H_2, e)$. This progress do not count each "nice pairs" (which are "edges" of $H$) multiple times.
05.02.2020 22:28
Thanks, got it.
09.02.2020 16:41
If $\varepsilon $ is a small positive real number then $(1+\varepsilon)\cdot v\sim v$. Let $G $ be a graph with $V $ vertices and $v$ edges such that $\mid E\mid=\mid V\mid=|v|$. $G $ does not consist $2$ cycles of equal lengths. If $G $ is a star graph with $V$ vertices $X;y_1,y_2,\cdots,y (v-1) $ and $v $ edges. $X $ is connected with $y_1,y_2,\cdots,y (v-1) $, $y_1$ is connected with $y_2$. The graph consists only $1$ cycle such that $y_1-X-y_2(\to y_1)$. A graph of $v $ edges will have only $2$ cycles, a contradiction. $G $ contains $(1+\varepsilon)\cdot v $ edges and if $\varepsilon $ is very small real positive number $\varepsilon\to 0$, $(1+\varepsilon)\to 1$. Edge number =$(1+\varepsilon)\cdot v\sim v $. $G $ has $v $ edges.
22.11.2020 21:20
Solved with help from p_square Take a spanning forest $T$ of $G$. Let $S$ be the graph on the $n$ vertices and having edge set as $E(S)=E(G)\setminus E(T)$. Note that $\vert E(S) \vert > \varepsilon n$. Note that $T$ is acyclic, so addition of every edge $e\in S$ to $T$, adds a unique cycle, which we call as $C_e$. Note that all the $C_e$ are unique. Thus there are atleast $\varepsilon n$ of these $C_e$ For every edge $t\in T$, let $f(t)$ denote the number of $C_e$ passing through $t$. We have a double count as : $$ \sum_{e\in S} \vert C_e \vert = \sum_{t\in T } f(t)$$ Note that the LHS is atleast $3+4+\dots+(\varepsilon n+2) > \tfrac 12 (\varepsilon n)^2$ So some edge $t$ of $T$ passes through atleast $\tfrac 12 \varepsilon^2n$ cycles. Delete $t$ and continue this process for the rest of the graph. Suppose $n > \left(\tfrac {8 \varepsilon^{-2}}{1+\epsilon}\right)^{1000}$.At any instant if we have deleted $s$ edges thm there is some edge in atleast $\tfrac 18 \varepsilon^2n$ cycles. Since there are atmost $n$ cycles, this algorithm terminates in atmost $8\varepsilon^{-2}$ steps. However this is less than $\varepsilon n$. Hence at the end we are left with a graph on $n$ vertices and $>n$ edges with no cycles. Absurd.$\square$
23.01.2021 02:00
Pathological wrote: Consider the number of members of the list which are in the interval $[k \sqrt{n}, (k+1) \sqrt{n})$. This is easily seen to be at most $\frac{\sqrt{n}}{\frac{k^2}{4}}+1 = \frac{4\sqrt{n}}{k^2}+1$. Can anybody explain this part, I am not able to see it immediately, and also shed some light on motivation for this approximation.
12.02.2021 08:31
Split the graph $G$ into connected components and let $\mathcal{T}$ be the forest formed by the union of the spanning trees of all components. Clearly the number of edges in $\mathcal{T}$ is $\leq n - c < n$ where $c$ is the number of connected components. Let $G' = G \backslash \mathcal{T}$, which consists of the remaining edges that connect two nodes of some tree, has $E > \epsilon n$ edges. Note that each distinct edge $e_i$ from $e_1, \ldots , e_{E} \in G'$ touches some tree in $\mathcal{T}$ at $u, v$, and forms a cycle $C_i = e_i \cup P(u, v)$ where $P(u, v)$ is the unique path from $u$ to $v$. Thus, across all edges in $G'$, we have $E$ distinct cycles $C_1, \ldots, C_{E}$. Now, we double count:\[\sum_{i = 1}^E (|C_i| - 1) = \sum_{e \in \mathcal{T}} \text{\#cycles containing $e$}\]where the LHS sums the number of edges of $C_i$ in $\mathcal{T}$ across all $C_i$. Assume FTSoC that the problem statement is false, and all cycles have different lengths. Then,\[\sum_{i = 1}^E (|C_i| - 1) \geq 2 + 3 + \ldots + (E + 1) = \frac{E(E + 3)}{2} > \frac{E^2}{2} > \frac{\epsilon^2n^2}{2}\]and since $\mathcal{T}$ has $< n$ edges, by Pigeonhole there is an edge $e \in \mathcal{T}$ that is part of $N > \frac{\epsilon^2n}{2}$ distinct cycles $C_i$. We will construct $kn^2$ more distinct cycles for some constant $k$, which suffices since quadratic growth eclipses linear growth for large enough $n$. Consider any two cycles $C_a, C_b$ induced by edges $e_a = \overline{u_av_a}, e_b = \overline{u_bv_b}$ that both contain $e = \overline{w_1w_2}$ where $w_2$ is further down the tree than $w_1$. Note that since $C_a, C_b$ contain $e$, it follows that at least one vertex from each of $e_a, e_b$ is further down the tree from $w_2$, WLOG $u_a$ and $u_b$. Then, \[C = P(u_a, u_b) \cup e_b \cup P(v_b, v_a) \cup e_a\]is clearly a new cycle, as $P(u_a, u_b)$ and $P(v_a, v_b)$ do not interfere with each other. Furthermore, since each such cycle is uniquely defined by $e_a, e_b$, every pair of edges generates a different cycle, for a total of\[\binom{N}{2} + N = \frac{N(N+1)}{2} > \frac{N^2}{2} > \frac{\epsilon^4n^2}{8}\]cycles, as desired. $\blacksquare$
20.03.2021 06:25
Consider a spanning forest of the graph $G$ consisting of spanning trees $T_1,T_2,\dots,T_k$ corresponding to connected components $G_1,G_2,\dots,G_k$ respectively. If some connected component $G_i$ with spanning tree $T_i$ has an edge $e$ outside $T_i$, this gives one immediate cycle from $T_i\cup e$: call such cycles critical. Hence there are at least \[3+4+\cdots+\varepsilon n=O(n^2)\]critical cycle-edge pairs, and some edge $t\in T_i$ for some $i$ is in at least $O(n)$ critical cycles: say it is in at least $cn$ critical cycles for some constant $c>0$ corresponding to different edges $e$ each. But then any two of these critical cycles $C_e$ and $C_{e'}$ corresponding to edges $e,e'$ respectively yield a cycle containing $e$ and $e'$, so there are $O(n^2)$ such cycles, absurd because there can only be $n$ total cycles at the most.
05.08.2021 12:39
Great problem! It's basically the same soln, but I would like to write it up. The main idea is the following: Get many cycles using the spanning forest of the graph (union of spanning trees of the components), and then combine in pairs some of these cycles to obtain new ones. Suppose that graph $G$ has $v$ vertices, more than $(1+e)v$ edges and all its cycles have distinct lengths. On the one hand, they are maximum $v$. We now find lower bound of their count. 1. Let $G_1, G_2,...,G_k$ be the connected components of $G$, and let $T_1, T_2,...,T_k$ be their spanning trees. Let $F$ be the union of these spanning trees (to motivate this, we want to spam cycles, and we can do so because if we add an edge to $F$, we get an cycle). Let $A$ the edges of $F$, and $B$ the rest. 2. For each edge $b$ not from $F$, let $C_b$ be the new cycle we get when we add $b$ to $F$. We will want to find an edge of $F$ (i.e. from $A$), which is included in many of the above cycles. To do this, take for each cycle $C_b$ the set $S_b$ of edges in $A$. Since each cycle $C_b$ has just one edge from $B$, and the others are from $A$, we find that the sets $S_b$ have pairwise different number of elements. Now you can do a bound of the numbers of all elements of $S_b$'s (which I won't write). So now we obtain that there is an edge in $A$, which is in more than $c$ cycles $C_b$. 3. Finally, let these cycles be of $b_1, b_2,...,b_m$. For each pair of these $b$'s, combine the two cycles containing $a$, and delete their common part to obtain just a cycle containing these $b$'s, and assign it to this pair of $b$'s. Now note that those cycles are distinct, so we now get an lower bound of the cycles in the graph.
19.06.2022 16:38
We first show that for any sufficiently large $n\geq N$, any connected simple graph $G$ with $n$ vertices and $(1+\varepsilon)n$ has two equal-length cycles. Consider a spanning tree $T$ of $G$ (with $n-1$ vertices). There are $\varepsilon n+1$ edges of $G$ not in $T$—call these special edges. Every special edge $e$ forms a distinct cycle $C(e)$ with exactly one special edge (itself) in it—call these special cycles. Suppose no two cycles have equal length, and mark each edge in $T$ with the number of special cycles passing through it. Since there are $\varepsilon n+1$ special cycles, and each special cycle of length $\ell$ contains $\ell-1$ edges in $T$, there are at least $$2+3+\cdots+(\varepsilon n+2)=\Theta(n^2)$$marks, so some edge $e \in T$ has at least $\tfrac{\Theta(n^2)}{n-1}=\Theta(n)$ marks. We can form a family of new, unique cycles by taking the XOR of any two cycles which pass through $e$. Clearly, there are $\binom{\Theta(n)}{2}=\Theta(n^2)$ such cycles. On the other hand, since we now found $\Theta(n^2)$ cycles with different lengths, we need at least $\Theta(n^2)$ vertices, but this is absurd as $(1+\varepsilon)n$ is $\Theta(n)$. To finish, we consider two cases for general $G$. If $G$ has a connected component with at least $N$ vertices, then we're done by considering only that connected component. Otherwise, there are an unbounded number of connected components with a cycle, otherwise for sufficiently large $n$ we have at most $n$ edges. Since there are finite number of graphs with cycles on at most $N-1$ cycles, by Pigeonhole for big enough $n$ there must be two isomorphic connected components. Clearly there would be two equal-length cycles by just considering these two components, so we're done in this case too. $\blacksquare$
12.08.2023 06:30
Used the 0\% hint on ARCH. Solved with \textbf{incompleteusern}, \textbf{tienxion}, and \textbf{hgomamogh}. It suffices to prove the result for when the graph is connected. This is because in any disconnected graph, if $R_1,R_2,\dots,R_k$ are the connected regions, we can add an edge between any vertex in $R_1$ and any vertex in $R_2$, any vertex in $R_2$ and any vertex in $R_3$, etc, until any vertex in $R_{k-1}$ and any vertex in $R_k$. We clearly have not introduced any new cycles, and the new graph also has at least $(1+\varepsilon)n$ edges. Since this new graph is connected, it has two cycles of the same length, so the original has them too. Now assume FTSOC that the graph does have $(1+\varepsilon)n$ edges and no two cycles have the same length. Then consider any spanning tree of the graph. This takes away $n-1$ edges(call these the \vocab{original edges}), so we have $\varepsilon n+1\sim \varepsilon n$ edges left. Call the leftover edges the \vocab{magic edges}. But each of these magic edges forms a cycle with some original edges. Call these original edges the \vocab{buddies} of a magic edge. Since the cycles must all have different length, the number of (buddy, magic) pairs is at least $\binom{\varepsilon n}{2}\ge \varepsilon_2 n^2$ for some positive real $\varepsilon_2$. So there exists some original edge that is the buddy of at least $\varepsilon_2 n$ magic edges. Call this original edge the \vocab{special edge}. The special edge splits the spanning tree into two parts(technically one of the parts can be a singleton vertex but whatever). Call one of these parts the \vocab{left part} and the other one the \vocab{right part}. Then consider any pair of distinct magic edges; say they are $AB$ and $CD$. Assume WLOG that $A$ and $C$ are in the left part while $B$ and $D$ are in the right part. Then there exists a cycle going from $A$ to $C$ along the spanning tree, then going from $C$ to $D$ along the magic edge, then going from $D$ to $B$ along the spanning tree, then going from $B$ to $A$ along the magic edge. Therefore, we have found at least $\binom{\varepsilon_2 n}{2}\ge \varepsilon_3 n^2$ cycles in the graph for some positive real $\varepsilon_3$. But there are clearly less than $n$ possible cycle lengths in a graph with $n$ vertices, so when $n$ is large enough we have a contradiction. $\blacksquare$
03.09.2023 22:06
Very nice and surprisingly simple problem, though it feels a bit easy for RMM3. Replace $v$ with $n$. Notice that we can assume WLOG that the graph is connected (else just add $O(1)$ edges.) Now take a spanning tree $T$ of $G$; the idea is that the extra $\varepsilon n$ edges create cycles. Assume for the sake of contradiction that there are no cycles of equal length. Then, notice that for each edge $e$ of the $\varepsilon n$ edges, there exists a cycle containing only $e$ and edges in $T$. Thus, by double counting, there exists an edge $e$ in $$N = \frac{3+4+\cdots + \varepsilon n + 2}n \sim \frac 12 \varepsilon^2 n$$cycles. On the other hand, for any two cycles containing this edge $e$, the composition of the two cycles minus $e$ creates a new cycle, which is obviously distinct for any pair of cycles (look at the points on the generated cycle that coincide with the endpoints of $e$.) As a result, there are at least $${N \choose 2} = \frac 18(\varepsilon^2 n)(\varepsilon^2 n - 2) \sim \varepsilon n^2$$cycles. For large enough $n$, this implies that there will be at least $n$ cycles, thus two of them must have the same length.
13.12.2023 23:37
FTSOC say all the cycles are distinct, with possible lengths $3, 4, 5, \dots$. Consider the $n-1$ edges that form spanning tree $T$ and place the the remaining $\epsilon n$ in $S$. Note that all cycles contain edges in $S$(Otherwise it would be in the spanning tree) Let $a_i$ denote the degree of $v_i$ in $S$. Note that for any vertex $v$, between any two neighbors $u_i, u_j \in S$, the graph $S\cup T$ has a cycle through $u_i-v-u_j$ since $u_i, u_j$ are connected in $T$ as well. Thus the number of pairs (vertex, cycle) can be counted by $\sum \binom{a_i}{2}$, and note that the minimum number of (vertex, cycle) pairs is $3 + 4 + \dots \epsilon n$ since we should be able to get a cycle of atleast any of those sizes including that number of the $S$ edges. However by jensens $\sum \binom{a_i}{2} \geq n\binom{2\epsilon}{2}$, which for large $n$ is less than $3 + 4 + \dots \epsilon n$. A contradiction $\blacksquare$. Remark: The idea of going ftsoc comes from the fact that two cycles of equal length is a pretty hard condition. Then noticing that due to the extra edges we know a lot of cycle lengths are possible makes you think of trying a more global approach.
09.02.2024 06:38
I am not 100% sure my solution works but here it is anyway. Claim 1: It is strictly stronger to look at $G$ being connected. Suppose the graph has $\geq 2$ connected components. Take any pair of connected components and draw an arbitrary edge $e$ connecting them. Note that since $e$ is between two connected components, it will not create any cycles, and thus will not produce two cycles of the same length if no such pair of cycles existed before adding $e$. Moreover, it strictly increases the number of edges and makes a stronger bound. Thus, we have reduced it to the connected case. $\square$ Since $G$ is connected, we may express it as some spanning tree $T$ with some collection of edges $e_1,e_2, \ldots, e_k$ where each $e_i$ connects two vertices in $T$. Claim 2: Given any $e_i \not = e_j$ there is a cycle in $G$ consisting only of $e_i$, $e_j$, and edges in $T$. Omitted for brevity (and laziness), I think this is pretty obviously true though. $\square$ Claim 3: If there are at least $n+C\sqrt{n}-1$ edges in $G$, where $C>10^{100}$, then there are two cycles of the same length. Notice that $T$ has $n-1$ edges, thus if we let $e_1,e_2, \ldots, e_k$ be the edges of $G$ not in $T$, then $k \geq C\sqrt{n}$. For each $e_i$ and $e_j$, we let $C_{i,j}$ denote the cycle through $e_i$ and $e_j$ described in claim 2. Note that each $C_{i,j}$ is distinct, thus there are at least $\binom{k}{2}$ such cycles. Since all these cycles are distinct lengths, there are at most $n$ of them. Thus, we get the inequality \[ \binom{k}{2} \leq n \implies k(k-1) \leq 2n \implies (k-1)^2 \leq 2n \]\[\implies k \leq \sqrt{2n}+1 \leq C\sqrt{n}\]For all $n \geq 1$. This implies the result of the problem since \[ 1 + \varepsilon \leq \frac{n+C\sqrt{n}}{n} = 1 + \frac{C}{\sqrt{n}} \]which is contradicted by taking $n > \left ( \frac{C}{\varepsilon} \right )^2$. Thus, we are done. $\blacksquare$
09.02.2024 12:23
blackbluecar wrote: Claim 2: Given any $e_i \not = e_j$ there is a cycle in $G$ consisting only of $e_i$, $e_j$, and edges in $T$. Omitted for brevity (and laziness), I think this is pretty obviously true though. $\square$ ... It seems obvious, but it's not true. See the tree on the picture and the two red edges ($e_i,e_j$). There is no cycle that contains these two edges. All the ideas used in the above solutions, including mine, circle around your approach, but some caution is needed to rule out bad cases as in the picture.
Attachments:

02.12.2024 01:26
Define an algorithm called cyclefinder, cyclefinder works by taking the largest cycle in a graph, removing all the vertice in it and repeating until it stops. It than outputs a value $f(G)$ where $G$ is a graph and $f(G)$ is the number of times cyclefinder preforms that operation until it stops. Claim: $f(G)<\sqrt{2n}$ if no two of those cycles are not the same length. Let $f(G)=k$, as none of the $k$ cycles are of the same length we have used at least $\frac{k(k+1)}{2}$ vertices. Thus as $\frac{\sqrt{2n}(\sqrt{2n}+1)}{2}>n$ we get that there are more vertices used than are available which is not possible so $f(G)<\sqrt{2n}$. Now take $n$ to be large enough that $\epsilon n>(\frac{1}{\epsilon}+2)\sqrt{2n}$, clearly such a value of $n$ exists. Now note that after we add $\sqrt{2n}$ edges we cannot add anymore edges without creating a new cycle beyond the distinct cycles, as we have at most $\sqrt{2n}$ distinct cycles and we can add an edges between any two of them without using a new vertice, any other edges we add beyond that use a new vertice. So we reach a position with at most $n+\sqrt{2n}$ edges such that any edge we add adds a new cycle. We can assume the graph is always connected as if we have two disconnected components we can use an edge to connect them without adding a cycle. So assume the graph is connected. We can connect each of the disconnected cycles without adding a cycle, than we can connect any remaining vertices, we know that any remaining vertices never form a cycle, so any more edges must be within the cycles or between the cycles. Note that if we have $k+1$ edges coming out from a cycle we can get $\frac{(k+1)(k+2)}{2}$ cycles. Thus the minimal number of cycles we can get from $k$ edges is when they are equally distributed between the cycles. Thus once we have at least $()\frac{1}{\epsilon}+1)\sqrt{2n}$ unused edges any extra edge we get assuming the edges are used optimally must add at least $\frac{1}{\epsilon}+1$ edges and we get an extra edge when $n$ increases by $\frac{1}{\epsilon}$, thus we get $\frac{1}{\epsilon}+1$ new cycles but only increase the length of the maximal cycle by $\frac{1}{\epsilon}$ so eventually we have the number of distinct cycles exceeds the length of the maximum cycle which means we have a repeat.
02.12.2024 06:50
Notice we can take WLOG $G$ to be a connected graph (else solve the problem taking all connected components which is just the same thing), so now take $T$ to be a spanning tree of $G$ Consider $U$ to be a subgraph of $G$ where all edges from $T$ are missing, and thus we would have $|E(U)|>\varepsilon n$, but the most important thing that matters when one realises this is the pick is that, adding any edge from $U$ back to the graph creates a new unique cycle that goes through exactly this edge and all the other edges belong to $T$, call any such cycle cool, meaning that there is at least $\varepsilon n$ new cool cycles created after restoring all the edges from $U$, consider an edge $e \in U$ then let $C_e$ be the cool cycle that was added at some point that goes through $e$ and $|C_e|$ will denote the number of vertices (or edges) it contains. As well let $\mathcal C_t$ to be the number of cool cycles that go through $t \in T$. Simple double counting gives: \[ \frac{\varepsilon^2 n^2}{2}<\frac{\varepsilon n(\varepsilon n+3)}{2}=2+3+\cdots+\varepsilon n+1 \le \sum_{e \in S} (|C_e|-1)=\sum_{t \in T} \mathcal C_t \]Therefore there must exist some $t \in T$ such that $\mathcal C_t > \frac{\varepsilon^2 n}{2}$, now lets forget about the cool cycles and focus on the normal cycles, for any two edges $e,e' \in S$ that span a cycle on $\mathcal C_t$, we made a new cycle going through both $e,e'$ and no other edge in $S$ so we can just select all possible pairs which gives at least $\binom{\tfrac{\varepsilon n}{2}}{2}$ new cycles generated this way. Therefore we have $O(n^2)$ spanning cycles from one single edge in $G$, each of different size, but this implies we could have at most $O(n)$ such cycles (from the problem conditions), thus we have achieved a contradiction for large enough $n$. Thus we can always set $v>N$ for which the problem is true, thus we are done .