Problem

Source: 2014 China TST 2 Day 2 Q5

Tags: combinatorics proposed, combinatorics, graph theory



Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The cycle of graph $G(V,E)$ is a set of distinct vertices ${v_1,v_2...,v_n}\subseteq V$, $v_iv_{i+1}\in E$ for all $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$; a cycle containing a chord is the cycle ${v_1,v_2...,v_n}$, such that there exist $i,j, 1< i-j< n-1$, satisfying $v_iv_j\in E$.