Problem

Source: ELMO Shortlist 2010, C8

Tags: graph theory, probability, expected value, combinatorics proposed, combinatorics



A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$? David Yang.