MathDB
Simple graph with 2 disjoint cycles, cycle contain chord

Source: 2014 China TST 2 Day 2 Q5

March 20, 2014
combinatorics proposedcombinatoricsgraph theory

Problem Statement

Find the smallest positive constant cc satisfying: For any simple graph G=G(V,E)G=G(V,E), if ∣E∣≥c∣V∣|E|\geq c|V|, then GG contains 22 cycles with no common vertex, and one of them contains a chord.
Note: The cycle of graph G(V,E)G(V,E) is a set of distinct vertices v1,v2...,vn⊆V{v_1,v_2...,v_n}\subseteq V, vivi+1∈Ev_iv_{i+1}\in E for all 1≤i≤n1\leq i\leq n (n≥3,vn+1=v1)(n\geq 3, v_{n+1}=v_1); a cycle containing a chord is the cycle v1,v2...,vn{v_1,v_2...,v_n}, such that there exist i,j,1<i−j<n−1i,j, 1< i-j< n-1, satisfying vivj∈Ev_iv_j\in E.
Back to ProblemsView on AoPS