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.
Problem
Source: ELMO Shortlist 2011, C5
Tags: logarithms, algorithm, combinatorics proposed, combinatorics
06.07.2012 15:01
In order to prove a) we use two facts: Fact 1. Every gtaph $G$ contains a cycle of length at least $\delta(G)+1$, providing $\delta(G) \geq 2$. Here $\delta(G) = \min_{v\in V(G)} \deg(v)$. Fact 2. Every graph $G$ has a subgraph $H$ with $\delta(H) > \frac{|E(G)|}{|V(G)|}$. Both propositions can be found in R.Diestel's "Graph Theory". These facts imply: Proposition 1. If $\frac{|E(G)|}{|V(G)|} \geq 2$ then $G$ contains a cycle with length at least $\frac{|E(G)|}{|V(G)|}.\, \square$ Let now denote $m=E(G)$. Proposition 1 yields that there exists a cycle with length at least $\frac{m}{n}$. Delete all edges of this cycle and there will remain $m_1=m(1-\frac{1}{n} )$ edges. So after $k$ steps there will remain $m_k= m(1-\frac{1}{n})^k$ edges. Here $m = O(n^2)$, so proceeding in this way guarantees $m_k$ will become $O(n)$ after $O(n\ln n)$ steps, which means that after $O(n\ln n)$ steps there will be no cycles to be removed (a forest will remain). Thus we proved a). Comment. Directly applying this method can not prove b), so it needs some fresh idea or somehow essentially to improve the above algorithm. I am very curious about the algorithm which could yield $O(n)$ cycles and a forest.
15.07.2012 03:41
dgrozev wrote: Comment. Directly applying this method can not prove b), so it needs some fresh idea or somehow essentially to improve the above algorithm. I am very curious about the algorithm which could yield $O(n)$ cycles and a forest. Hmm, David does not seem to remember his solution. All I know is that it involved Vinogradov's theorem, i.e. the fact that every sufficiently large odd number is the sum of three primes... perhaps he made a mistake, I dunno.
09.04.2019 15:07
Could anyone post a solution to b)? Knowing that it's connected with Vinogradov's theorem does not help me......
13.03.2024 05:05
It was pointed out to me some time ago that part b would imply the Erdos-Gallai cycle decomposition conjecture which is still open, so I'm not sure if dyang fakesolved or if he is just a genius