Prove that G has a triangle-free induced subgraph with at least $\frac{n}{15 \sqrt{3}}$ vertices. Problem: 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.
Proof Given:
Choose a subgraph $H \subset G$ by picking each vertex independently with probability $p \in[0,1]$, to be determined. Let $X = |V(H)|$, the number of chosen vertices. Let $A_v$ be the event that v is in a triangle and $Y_v$ be its indicator. Then $Y = \sum_{v \in H} Y_v$ is the number of "bad" vertices. Then the number of "good" vertices (not in a triangle) is $X-Y$.
$$E[X-Y] = E[X] -E[Y] = np-100n\cdot p^3 = n(p-100p^3)$$
Consider the function $f(p) = p-100p^3$.
Then, $f'(p)=1-300p^2$ and $f'(p)=0$ for $p=\frac{1}{\sqrt{300}}=\frac{1}{10\sqrt{3}}$, i.e. $f(p)$ is maximized at $p=\frac{1}{10\sqrt{3}}$.
Let $p=\frac{1}{10\sqrt{3}}$.
Then,
$$E[X-Y] = n(\frac{1}{10\sqrt{3}}-\frac{100}{1000\sqrt{3}})^3) = n(\frac{1}{10\sqrt{3}}- \frac{1}{10\sqrt{3}^3}) = \frac{n}{15\sqrt{3}}$$
So there must exist a subgraph with at least ${n\over 15\sqrt{3}}$ vertices that has no triangle.
My question is, why is $E[Y] = 100np^3$? Is this actually an upper bound on $E[Y]$?
 A: I would say that the random process is poorly described. The idea is:

*

*We choose a subgraph $H$ of $G$, by including each vertex with probability $p$.

*For every triangle in $H$, we mark one arbitrary vertex of that triangle.

*We choose a smaller subgraph $H'$ of $H$ by keeping only those vertices of $H$ which were not marked. (In particular, $H'$ does not have any triangles, because each triangle contains a marked vertex.)

Now, $X$ can be the number of vertices in $H$ (as in the proof you gave) and $Y$ can be the number of triangles. The expected number of triangles $\mathbb E[Y]$ is at most $100 np^3$ by linearity of expectation: there are at most $100n$ triangles in $G$, and each one is a triangle in $H$ with probability $p^3$.
Then the number of marked vertices is at most $Y$: here, there is another "at most" because a vertex could get marked multiple times by multiple triangles that contain it.
Finally, this means that the number of vertices in $H'$ is at least $X-Y$, and from there the proof continues as written.
