Theorem 4.1.1. The Goodman Bound [136].
Let \(G\) be a graph and let \(p = 2|E(G)|/|V(G)|^2\text{.}\) The number of triangles in \(G\) is at least
\begin{equation*}
p(2p-1)|V(G)|^3/6\text{.}
\end{equation*}
Section 4.1 Supersaturation for Triangles
Our next aim is to give a very nice argument of Goodman [136] which gives a nearly-optimal supersaturation result in the case that \(H\) is a triangle. This can be thought of as a quantitative strengthening of Mantel’s Theorem for graphs with more than \(n^2/4\) edges.
“Triangles in a graph.”
Proof.
We follow an argument similar to the proof of Mantel’s Theorem. Let \(t\) be the number of triangles in \(G\) and, for each edge \(uv\in E(G)\text{,}\) let \(t_{uv}\) be the number of triangles which contain \(uv\text{.}\) Of course, \(t_{uv}\) is precisely \(|N(u)\cap N(v)|\text{.}\) So, for any \(uv\in E(G)\text{,}\)
\begin{equation*}
d(u)+d(v)=|N(u)\setminus N(v)|+|N(v)\setminus N(u)|+ 2|N(u)\cap N(v)|
\end{equation*}
\begin{equation*}
\leq |V(G)| + t_{uv}\text{.}
\end{equation*}
By Lemma 3.1.5,
\begin{equation*}
\sum_{v\in V(G)}d(v)^2 = \sum_{uv\in E(G)}(d(u)+d(v))\leq |E(G)||V(G)| + \sum_{uv\in E(G)}t_{uv}
\end{equation*}
\begin{equation*}
=|E(G)||V(G)|+3t
\end{equation*}
(since the sum \(\sum_{uv\in E(G)}t_{uv}\) counts every triangle thrice). Combining this with the handshaking lemma and Corollary C.0.6,
\begin{equation*}
4|E(G)|^2 = \left(\sum_{v\in V(G)}d(v)\right)^2 \leq |V(G)|\sum_{v\in V(G)}d(v)^2
\end{equation*}
\begin{equation*}
\leq |V(G)|^2|E(G)| + 3|V(G)|t\text{.}
\end{equation*}
Thus, by definition of \(p\text{,}\) we have
\begin{equation*}
t\geq \frac{4|E(G)|^2}{3|V(G)|} - \frac{|V(G)||E(G)|}{3} = \frac{p^2|V(G)|^3}{3} - \frac{p|V(G)|^3}{6}\text{.}
\end{equation*}
This completes the proof.
Note that the quadratic \(p(2p-1)\) is non-negative whenever \(p\geq1/2\text{.}\) Therefore, the Goodman Bound implies Mantel’s Theorem (Theorem 3.1.4).
Here are a couple of YouTube videos related to Goodman’s Bound:
