How do I prove that a non-abelian group would have at least $6$ elements? I can always show that a non-abelian group would have 5 distinct elements $1,a, b, ab, ba$, since $ab\neq ba$. Is there any formal proof for this?
 A: You can show that every group upto order $5$ is Abelian and give an example of a non-Abelian group of order $6$. This would show that a non-Abelian group must have at least $6$ elements.

Clearly, the trivial group is Abelian. Groups of order $2,3$ and $5$ have prime order. Thus, they are cyclic, hence Abelian.

So, we are just left to show that a group of order $4$ needs to be Abelian.

Let $G$ be a group of order $4$. If $G$ is cyclic, then we're done. If not, then there does not exist an element of order $4$ in $G$. Thus, by Lagrange's theorem all non-identity elements must have order $2$. Thus $$(xy)(xy)=e$$ for all $x,y \in G$. Hence, $$(yx)(xy)(xy)=yx\\xy=yx$$ for all $x,y\in G$. This shows $G$ is Abelian.

So, we have shown every group upto order $5$ is Abelian. $S_3$ is an example of a non-Abelian group of order $6$.
A: You proved correctly that a non-abelian group $G$ must have at least $5$ elements. Could it have only $5$ element? No, because then $\langle a\rangle$ would have to have $5$ elements (by Lagrange's theorem and because $5$ is prime) and therefore $b\in\langle a\rangle$. But this is impossible, since $ab\neq ba$. Therefore, $G$ has at least $6$ elements.
A: This can be shown by complete elementary means, that is, without any appeal to Lagrange's Theorem or any theorem whatsoever. 
Case $|G|=1$ or $2$: trivial
Case $|G|=3$: let $G=\{e,g_1,g_2\}$, all elements different. Look at $g_1g_2$. Since $G$ is closed, $g_1g_2=e$ or $g_1g_2=g_1$ or $g_1g_2=g_2$. In the first case $g_2=g_1^{-1}$ and the group is abelian. The second and third case imply $g_2=e$ or $g_1=e$, both contradictions.
Case $|G|=4$: assume that $G$ is not abelian, then we can find to different elements, say (after renumbering) $g_1$ and $g_2$, not equal to the identity, such that $g_1g_2 \neq g_2g_1$. It follows that the elements in the set $\{e,g_1,g_2, g_1g_2\}$ are all different. Hence $G=\{e,g_1,g_2, g_1g_2\}$. Now look at $g_2g_1$. This element does not equal $e$, since $g_1$ and $g_2$ do not commute so these elements cannot be each other inverse. It can't be $g_1$ neither $g_2$ because $g_1 \neq e \neq g_2$. Conclusion: $g_2g_1=g_1g_2$, a contradiction. 
Case $|G|=5$: (sketch) suppose $G$ is not abelian. Then you can find two different elements, say (after renumbering) $g_1$ and $g_2$, not equal to the identity, such that $g_1g_2 \neq g_2g_1$. Then the elements $\{e, g_1,g_2, g_1g_2, g_2g_1\}$ are all different. Now try to derive a contradiction (look at $g_1^2$ - which element of the set is this? Do the same for $g_1g_2g_1$).
