Problem 2130

Solution:
Fix a positive real number $\varepsilon$, and let $G$ be a graph on $v$ vertices with at least $(1+\varepsilon) v$ edges, all of whose simple cycles have pairwise distinct lengths.
Assuming $\varepsilon^{2} v \geq 1$, we exhibit an upper bound linear in $v$ and a lower bound quadratic in $v$ for the total number of simple cycles in $G$, showing thereby that $v$ cannot be arbitrarily large, whence the conclusion.
Since a simple cycle in $G$ has at most $v$ vertices, and each length class contains at most one such, $G$ has at most $v$ pairwise distinct simple cycles. This establishes the desired upper bound.
For the lower bound, consider a spanning tree for each component of $G$, and collect them all together to form a spanning forest $F$. Let $A$ be the set of edges of $F$, and let $B$ be the set of all other edges of $G$. Clearly, $|A| \leq v-1$, so $|B| \geq (1+\varepsilon) v - |A| \geq (1+\varepsilon) v - (v-1) = \varepsilon v + 1 > \varepsilon v$.
For each edge $b$ in $B$, adjoining $b$ to $F$ produces a unique simple cycle $C_{b}$ through $b$. Let $S_{b}$ be the set of edges in $A$ along $C_{b}$. Since the $C_{b}$ have pairwise distinct lengths, $\sum_{b \in B} |S_{b}| \geq 2 + \cdots + (|B|+1) = |B|(|B|+3)/2 > |B|^{2}/2 > \varepsilon^{2} v^{2}/2$.
Consequently, some edge in $A$ lies in more than $\varepsilon^{2} v^{2}/(2v) = \varepsilon^{2} v/2$ of the $S_{b}$. Fix such an edge $a$ in $A$, and let $B'$ be the set of all edges $b$ in $B$ whose corresponding $S_{b}$ contain $a$, so $|B'| > \varepsilon^{2} v/2$.
For each 2-edge subset $\{b_{1}, b_{2}\}$ of $B'$, the union $C_{b_{1}} \cup C_{b_{2}}$ of the cycles $C_{b_{1}}$ and $C_{b_{2}}$ forms a $\theta$-graph, since their common part is a path in $F$ through $a$; and since neither of the $b_{i}$ lies along this path, $C_{b_{1}} \cup C_{b_{2}}$ contains a third simple cycle $C_{b_{1}, b_{2}}$ through both $b_{1}$ and $b_{2}$. Finally, since $B' \cap C_{b_{1}, b_{2}} = \{b_{1}, b_{2}\}$, the assignment $\{b_{1}, b_{2}\} \mapsto C_{b_{1}, b_{2}}$ is injective, so the total number of simple cycles in $G$ is at least $\binom{|B'|}{2} > \binom{\varepsilon^{2} v/2}{2}$. This establishes the desired lower bound and concludes the proof.

Sketch of solution 2. (Po-Shen Loh)
Recall that the girth of a graph $G$ is the minimal length of a (simple) cycle in this graph.
Lemma. For any fixed positive $\delta$, a graph on $v$ vertices whose girth is at least $\delta v$ has at most $v+o(v)$ edges.
Proof. Define $f(v)$ to be the maximal number $f$ such that a graph on $v$ vertices whose girth is at least $\delta v$ may have $v+f$ edges. We are interested in the recursive estimates for $f$.
Let $G$ be a graph on $v$ vertices whose girth is at least $\delta v$ containing $v+f(v)$ edges. If $G$ contains a leaf (i.e., a vertex of degree 1), then one may remove this vertex along with its edge, obtaining a graph with at most $v-1+f(v-1)$ edges. Thus, in this case $f(v) \leq f(v-1)$.
Define an isolated path of length $k$ to be a sequence of vertices $v_{0}, v_{1}, \ldots, v_{k}$, such that $v_{i}$ is connected to $v_{i+1}$, and each of the vertices $v_{1}, \ldots, v_{k-1}$ has degree 2 (so, these vertices are connected only to their neighbors in the path). If $G$ contains an isolated path $v_{0}, \ldots, v_{k}$ of length, say, $k > \sqrt{v}$, then one may remove all its middle vertices $v_{1}, \ldots, v_{k-1}$, along with all their $k$ edges. We obtain a graph on $v-k+1$ vertices with at most $(v-k+1)+f(v-k+1)$ edges. Thus, in this case $f(v) \leq f(v-k+1)+1$.
Assume now that the lengths of all isolated paths do not exceed $\sqrt{v}$; we show that in this case $v$ is bounded from above. For that purpose, we replace each maximal isolated path by an edge between its endpoints, removing all middle vertices. We obtain a graph $H$ whose girth is at least $\delta v / \sqrt{v} = \delta \sqrt{v}$. Each vertex of $H$ has degree at least 3. By the girth condition, the neighborhood of any vertex $x$ of radius $r = \lfloor (\delta \sqrt{v} - 1)/2 \rfloor$ is a tree rooted at $x$. Any vertex at level $i < r$ has at least two sons; so the tree contains at least $2^{\lfloor (\delta \sqrt{v} - 1)/2 \rfloor}$ vertices (even at the last level). So, $v \geq 2^{\lfloor (\delta \sqrt{v} - 1)/2 \rfloor}$ which may happen only for a finite number of values of $v$.
Thus, for all large enough values of $v$, we have either $f(v) \leq f(v-1)$ or $f(v) \leq f(v-k+1)$ for some $k > \sqrt{v}$. This easily yields $f(v) = o(v)$, as desired.

Now we proceed to the problem. Consider a graph on $v$ vertices containing no two simple cycles of the same length. Take its $\lfloor \varepsilon v / 2 \rfloor$ shortest cycles (or all its cycles, if their total number is smaller) and remove an edge from each. We get a graph of girth at least $\varepsilon v / 2$. By the lemma, the number of edges in the obtained graph is at most $v + o(v)$, so the number of edges in the initial graph is at most $v + \varepsilon v / 2 + o(v)$, which is smaller than $(1+\varepsilon) v$ if $v$ is large enough.