From Section $2.12$ of Herstein's "Topics in Algebra" ($2^{\text{nd}}$ edition):
$\;$ We give one other illustration of the use of the various parts of Sylow's theorem. Let $G$ be a group of order $72$; $o(G) = 2^{3}3^{2}$. How many $3$-Sylow subgroups can there be in $G$? If this number is $t$, then, according to Theorem $2.12.3$, $t = 1 + 3k$. According to Lemma $2.12.5$, $t \mid 72$, and since $t$ is prime to $3$, we must have $t \mid 8$. The only factors of $8$ of the form $1 + 3k$ are $1$ and $4$; hence $t = 1$ or $t = 4$ are the only possibilities. In other words $G$ has either one $3$-Sylow subgroup or $4$ such.
$\;$ If $G$ has only one $3$-Sylow subgroup, since all $3$-Sylow subgroups are conjugate, this $3$-Sylow subgroup must be normal in $G$. In this case $G$ would certainly contain a nontrivial normal subgroup. On the other hand if the number of $3$-Sylow subgroups of $G$ is $4$, by Lemma $2.12.5$ the index of $N$ in $G$ is $4$, where $N$ is the normalizer of a $3$-Sylow subgroup. But $72 \nmid 4! = (i(N))!$. By Lemma $2.9.1$ $N$ must contain a nontrivial subgroup of $G$ (of order at least $3$).
It is the last part that I don't understand. Since the the normalizer $N$ is of order $18$ in this example, why must the order of the normal subgroup that $N$ contains be at least $3$? That is, why can't $N$ only have one normal subgroup, of order $2$?
Clarifying notes:
By $i(N)$, Herstein means the index of the subgroup $N$.
For reference, here is Lemma $2.9.1$, Lemma $2.12.6^{*}$, and Theorem $2.12.3$:
Lemma $2.9.1$:
If $G$ is a finite group, and $H \neq G$ is a subgroup of $G$ such that $o(G) \nmid i(H)!$ then $H$ must contain a nontrivial normal subgroup of $N$. In particular, $G$ cannot be simple.
Lemma $2.12.6$:
The number of $p$-Sylow subgroups in $G$ equals $o(G) / o(N(P))$, where $P$ is any $p$-Sylow subgroup of $G$. In particular, this number is a divisor of $G$.
Note that $N(P)$ in the above lemma is the normalizer of $P$
Theorem $2.12.3$:
The number of $p$-Sylow subgroups in $G$, for a given prime, is of the form $1 + kp$.
$^{*}$The book mistakenly references Lemma $2.12.5$ in place of Lemma $2.12.6$, I think, which is why I include Lemma $2.12.6$ instead of Lemma $2.12.5$.
Best Answer
If $G$ is a group, and $H$ is a subgroup of index $k\gt 1$, then the action of $G$ on the left cosets of $H$ induces a nontrivial homomorphism $G\to S_k$. In particular, if $|G|$ does not divide $k!$, the order of $S_k$, then this homomorphism cannot be one-to-one, so its kernel is a nontrivial normal subgroup of $G$. This is how you get Lemma 2.9.1.
So here you have that if $N$ has index $4$, then the action of $G$ on the left cosets of $N$ gives a homomorphism $G\to S_4$. Since $|G|=72$ does not divide $4!$, the kernel of this map is nontrivial.
What size can the kernel have? If $M$ is the kernel, then $|G|/|M|$ must divide $4!=24$ by Lagrange's Theorem: the First Isomorphism Theorem tells you that $G/M$ is isomorphic to a subgroup of $S_4$. So the size of $M$ must be at least $3$: $|M|=2$ wouldn't work, because $|G|/2 = 36$ is still too large.