Let $|G|=p^a$. Prove that if $|N|=p^{a-1}\Rightarrow N\lhd G$
If $a=1$ this is straightforward because $G$ is abelian and every group is normal, in particular $N$. Let us take $a>1$.
First try: If we use the orbit stabilizer theorem, this yields:
$$p^{a-1}=|N|=|\dot{\cup}_i G*n_i|=\sum_i |G*n_i|=\sum_i[G:G_{n_i}]$$
If $[G:G_{n_i}]=1$ this means that $g*n=gng^{-1}=n$ for every $g\in G$. In other words $n\in Z(G)$. So we need:
$$p^{a-1}=|N\cap Z(G)|+\sum_{[G:G_{n_i}]>1}[G:G_{n_i}]$$
If we are able to prove there is no $[G:G_{n_i}]>1$ we are done because that would mean $N\subset Z(G)$ and then it would need to be normal. Not sure how to prove this.
Second try: because that didn't work very nicely, I tried considering the center of $N$, that is $C(N)=\{g\in G | gNg^{-1}\subset N\}$. It is clear $C(N)$ is a group and $N\subset C(N)$. By Lagrange's Theorem $|C(N)|=p^{a-1}$ or $|C(N)|=p^a$. If the second case holds, this means $N\lhd G$. So we just need to show $|C(N)|=p^{a-1}$ is impossible.
If $C(N)=p^{a-1}$, then $C(N)=N$ and for every $x\in G\cap N^C$ we have $xNx^{-1}\not \subset N$. Because $\Phi_x$ is an automorphism $|xNx^{-1}|=p^{a-1}$. There are $p^a-p^{a-1}$ elements $x_j$ such that $|x_jNx^{-1}_j|=p^{a-1}$ and $x_jNx_j^{-1}\not\subset N$. This is also not very promissing.
Any suggestions ?
Standard Theorem : Suppose $G$ is a finite group and $p$ is the smallest prime dividing the order of $G$. Then, any subgroup of $G$ of index $p$ is normal in $G$.
Proof : Suppose $H$ is such a subgroup. Consider the action of $G$ on the set $G/H$ of left cosets of $H$ in $G$ by, $g.aH = (ga)H$. Consider the associated permutation representation $\phi : G \rightarrow S_{G/H}$. Let $K$ be its kernel. Clearly, $K \subseteq H$.
Now, the first isomorphism theorem applied to the homomorphism $\phi$ implies that $[G : K] | |G/H|! = p!$. But, $[G:K] = [G:H].[H:K] = p.[H:K]$, so that $[H:K]|(p-1)!$. If $[H:K] > 1$, there is a prime $q$ dividing it and hence, $q$ divides $|G|$. By minimality of the prime $p$, $p \leq q$. But then, $q|(p-1)!$ is a contradiction.
Hence, $[H:K] =1$. Hence, $H=K$ is a normal subgroup of $G$.