Equivalence of statements of Triangle Removal Lemma There are two different statements that are supposed to be equivalent reformulations of the Triangle Removal Lemma from combinatorics. One says that given any $f(n)\in o(n^3)$, there is some $g(n)\in o(n^2)$ such that any $n$-vertex graph with at most $f(n)$ triangles can be made triangle-free by removing at most $g(n)$ edges. Another states that for every $\epsilon > 0$, there is some $\delta(\epsilon)>0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles can be made triangle-free by eliminating at most $\epsilon n^2$ edges.
Now in this question, the second of these was shown to imply the first. As inept as this sounds, I was simply unable to see why the first implies the second. More generally, I have a major lack of intuition as to why these might be equivalent statements: the first says that for any $f(n)$ (which controls the triangles) there is some $g(n)$ (controlling the edges) whereas the second version says that for every $\epsilon$ (controlling the edges) there is some $\delta$ (controlling the triangles), thus my intuition is crying out to me saying that the quantifiers have been reversed so these statements can't possibly encode the same information.
Could someone explain why first of these statements implies the second and, if possible, why my (intuitive/soft) concern about quantifier reversal isn't correct?
 A: Why the quantifiers cannot be any other way
First of all, let me address what's going on with quantifier reversal.
We may check that out of 8 possibilities for the quantifiers (we may put $\forall$ or $\exists$ on each variable, and we can put them in either order):

*

*The only interesting way to state the first lemma is $\forall f(n) \in o(n^3)$ $\exists g(n) \in o(n^2)$.

*The only interesting way to state the second lemma is $\forall \epsilon>0$ $\exists \delta>0$.

I will not check all $16$ cases here, they're mostly boring, but here is why neither lemma can be stated in the form of the other.
If we state the first lemma as $\forall g(n) \in o(n^2)$ $\exists f(n) \in o(n^3)$, we state a much weaker result. The proof is: for any $g(n) \in o(n^2)$, pick $f(n) = g(n)$. It is true that in an $n$-vertex graph with at most $g(n)$ triangles, we can delete at most $g(n)$ edges and get a triangle-free graph: delete an arbitrary edge from each triangle.
If we state the second lemma as $\forall \delta>0$ $\exists \epsilon>0$, we also state a much weaker result. The proof is: for any $\delta>0$, pick $\epsilon = \frac12$. It is true that in an $n$-vertex graph with any number of triangles you like, we can delete at most $\frac12n^2$ edges and get a triangle-free graph: delete all the edges.
Why these quantifiers actually make sense together
Okay, but why is this happening?
The reason is that there are extra quantifiers hidden inside the $o(n^2)$ and $o(n^3)$:

*

*We can unpack "$f(n) \in o(n^3)$" as "for every $\delta>0$, there is an $n_0$ such that if $n>n_0$, then $f(n) \le \delta n^3$. Since we assume we are given an $f(n) \in o(n^3)$, this definition lets us pick any $\delta>0$ we like and assume our graph has at most $\delta n^3$ triangles - just by taking $n$ large enough. This is a lot like proving $\exists \delta > 0$, which also lets us pick $\delta$.

*We can unpack "$g(n) \in o(n^2)$" as "for every $\epsilon>0$, there is an $n_0$ such that if $n>n_0$, then $g(n) \le \epsilon n^2$. In order to construct $g(n)$, we must make sure that for all $\epsilon>0$, there is a large enough $n$ that we only delete at most $\epsilon n^2$ edges. From point 1, "large enough $n$" means "we can pick the $\delta>0$ we want".

These hidden quantifiers inside the little-o statements of the first lemma are actually the quantifiers corresponding to the visible quantifiers of the second lemma.
Why the first lemma implies the second
This is a bit long, and essentially the reason for that is we need triangle removal to give us a "nice" dependency between triangles and edges. The $o(n^3)$ and $o(n^2)$ only say what is going on as $n \to \infty$, and we'll need to work to fill in the gaps.
Let $\epsilon>0$. Define $f(n)$ as follows: for each $n$, $f(n)$ is the largest value $t \in \{0,\dots,\binom n3\}$ such that the statement "If an $n$-vertex graph has at most $t$ triangles, it can be made triangle-free by removing at most $\frac14\epsilon n^2$ edges" holds.
If $f(n)$ were $o(n^3)$, then the first lemma would actually give us much more: a function $g(n)$ which is $o(n^2)$, and can replace $\frac14\epsilon n^2$ in the statement above. Eventually, for large enough $n$, $g(n)$ is less than $\frac14\epsilon n^2 - 1$. At this point, if a graph has at most $f(n)+1$ triangles, it can also be made triangle-free by removing at most $\frac14\epsilon n^2$ edges: remove a single edge from some triangle (leaving at most $f(n)$ triangles), then remove $g(n)$ more edges to destroy all remaining triangles. This contradicts our choice of $f(n)$: for this $n$, it could have been $1$ higher!
Therefore $f(n)$ is not $o(n^3)$. In other words, there is a $\delta>0$ such that for infinitely many values of $n$ we have $f(n) > \delta n^3$.
But we need the proof to work for arbitrary $n$, not just for these special values. So take any $n$ and take any $n$-vertex graph with at most $\delta n^3$ triangles, then choose some $m > 10n$ such that $f(m) > \delta m^3$. Write $m = qn + r$ with $0 \le r < n$, noting that our choice of $m$ means $q \ge 10$.
From $G$, construct an $m$-vertex graph $H$ by replacing every vertex of $G$ by $q$ vertices and every edge by a copy of $K_{q,q}$, then adding $r$ isolated vertices. Each triangle in $G$ corresponds to a complete tripartite graph $T \cong K_{q,q,q}$ in $H$, with $q^3$ triangles, and there are no other triangles in $H$, thus $H$ has at most $\delta n^3 q^3 \le \delta m^3$ triangles. Therefore it is possible to remove $\frac14 \epsilon m^2$ edges from $H$ to make it triangle-free.
Now we try to imitate that edge deletion in $G$, with some loss of efficiency. Delete from $G$ every edge such that the corresponding copy of $K_{q,q}$ in $H$ lost at least $\frac13 q^2$ of its edges. This cannot delete more than $\epsilon n^2$ edges, because then we'd be deleting $(\frac13q^2)(\epsilon n^2) > \frac14 \epsilon m^2$ edges from $H$. (Here we use $m < qn+n$ and $q \ge 10$.) Now we must check that this destroys every triangle in $G$.
Each triangle in $G$, again, corresponds to a complete tripartite graph $T \cong K_{q,q,q}$ in $H$, with $q^3$ triangles, and each edge of $T$ is contained in only $q$ of those triangles, so at least $q^2$ of the $3q^2$ edges in $T$ are deleted when $H$ is made triangle-free. By averaging, one of the three copies of $K_{q,q}$ in $T$ loses at least $\frac13 q^2$ of its edges. Therefore one of the edges of this triangle in $G$ will be deleted by the rule in the previous paragraph.
So we've successfully removed all triangles from $G$ with only $\epsilon n^2$ deleted edges.
A: While I don't think it would be good form to change the status of the accepted answer from the current one to this so long after the question was answered, the comments below that answer show that the proof presented there isn't exactly water tight and indeed it's not completely obvious to me (though maybe it is to Professor Lavrov, as I am much less experienced) how to alter the proof to make the details clear. After some thought, I came up with the following argument that as I understand works entirely for the implication I was interested in. I am indebted to Misha Lavrov, however, for helping with the intuition.

Suppose the first lemma held and the second lemma did not for contradiction, i.e. suppose that there is some $\varepsilon > 0$ such that for all $m \in \mathbb{N}$ there is some graph $G_m$ with $n = n(m)$ vertices, at most $\frac{n^3}{m}$ triangles and yet cannot be made triangle-free by removing at most $\varepsilon n^2$ edges. Note that if there is such a counterexample to the original statement for a given $m$, there are counterexamples for that same $m$ with arbitrarily large numbers of vertices (for example we could take disjoint copies of $G_m$) and thus we may assume WLOG that $n(m)$ is a strictly increasing function of $m$.
We then define $f(n) = \frac{n^3}{m_0(n)}$ where $m_0(k) = \min \{ m\,|\, n(m)>k\}$. Since $m_0(n)\to \infty$ as $n\to \infty$ we know that $\frac{f(n)}{n^3} = \frac{1}{m_0(n)}\to 0$ so $f(n) \in o(n^3)$ and thus we get a function $g(n)\in o(n^2)$ satisfying the properties of the first lemma.
Since $g(n)\in o(n^2)$, we know that there is some $N$ such that for all $k>N$ we have $g(k)<\varepsilon k^2$ we have $g(k) < \epsilon k^2$. But we also know that for $k>N$ that there existed (taking $m = m_0(k)$ in the original assumption above) $G_{m_0(k)}$ which:

*

*has $n = n(m_0(k)) > k$ vertices

*has at most $\frac{n(m)^3}{m} \leq \frac{n(m)^3}{m_0(n(m))} = f(n)$ triangles

*cannot be made triangle-free by removing at most $\varepsilon n^2$ edges.

However, we can make it triangle-free by removing $g(n)$ edges and $\varepsilon n^2 > g(n)$ since $n > k > N$ so we reach a  contradiction.
