Problem

Source: Iran 3rd round 2013 - Combinatorics exam problem 5

Tags: function, combinatorics, graph theory



Consider a graph with $n$ vertices and $\frac{7n}{4}$ edges. (a) Prove that there are two cycles of equal length. (25 points) (b) Can you give a smaller function than $\frac{7n}{4}$ that still fits in part (a)? Prove your claim. We say function $a(n)$ is smaller than $b(n)$ if there exists an $N$ such that for each $n>N$ ,$a(n)<b(n)$ (At most 5 points) Proposed by Afrooz Jabal'ameli