Let $G$ be an $n$-vertex graph with at most $100n$ triangles. Prove that $G$ has a triangle-free induced subgraph with at least $\frac{n}{15 \sqrt{3}}$ vertices.
My solution:
We pick each vertex independently with probability $p \in[0,1]$ (we choose it later). Let $X$ be a number of chosen vertices and $Y$ a number of chosen triangles. Then the number of good vertices is at least $X-Y$ (we throw out from each chosen triangle at least one (bad) vertex). Calculate the expectation of it.
$$E(X-Y) = E(X) -E(Y) \geq np-100n\cdot p^3$$ Now, the function $f(p) = p-100p^3$ has maximum at $p={\sqrt{3}\over 30}$ which give us $$E(X-Y) \geq {n\over 15\sqrt{3}}$$
So there must exists a subgraph with at least ${n\over 15\sqrt{3}}$ vertices with no triangle.
Now I have 2 questions:
- Is there a non probabilistic solution?
- Is there a better bound?
Here is an upper bound of $\frac{n}{13}$, i.e. a graph such that every $\frac{n}{13}+1$ vertices induce a subgraph containing a triangle.
Let $n$ be a multiple of $26$, and let $G$ be $\frac{n}{26}$ disjoint copies of $K_{26}$. The number of triangles is ${26 \choose 3}\frac{n}{26} = 100n$, and clearly the largest number of vertices such that the induced subgraph is triangle-free is $2\frac{n}{26} = \frac{n}{13}$.