Problem

Source: ELMO Shortlist 2011, C5

Tags: logarithms, algorithm, combinatorics proposed, combinatorics



Prove there exists a constant $c$ (independent of $n$) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where a) $f(n)=n\ln{n}$; b) $f(n)=n$. David Yang.