What is the most elementary proof of the following: a non-abelian group of order $6$ is isomorphic to $S_3$ We know that, a non-abelian group of order $6$ is isomorphic to $S_3$. While I've been able to locate different proofs of this result, I would like to have one that is as elementary as it can be. So is there a proof that uses only the more elementary facts about groups such as the uniqueness of the identity; the uniquness of the inverses; the cancellation laws; the Lagrange's theorem and its corollaries; or the concepts of the homomorphisms, the normal subgroups,  and the quotient groups? 
 A: [Rewritten to eliminate Cauchy's theorem.]
First I argue there is an element $a$ of order 2 and an element $b$ of order 3.  By Lagrange's theorem each element other than the identity has order 2, 3, or 6. The argument that every group with even order has an element of order $2$ is brief and elementary: Just define an equivalence relation $x \sim y \iff x = y$ or $xy = 1$ and count equivalence classes.
So it just remains to show that $G$ has an element of order $3$: To this end, it is possible to prove the much more general fact that

If $G$ is a group in which every non-identity element has order $2$, then $G$ is abelian.

To prove this, note that if $x, y \in G$, we have
$$xxyy = x^2 y^2 = 1 = (xy)^2 = xyxy$$
Cancelling on both sides, $xy = yx$, and $G$ is abelian. 
Thus the group (call it $G$) contains an element of order 2 and an element of order 3, which we may call $a$ and $b$.  Then it is elementary that $$\{1, a, b, ab, b^2, ab^2\}$$ are all distinct and so exhaust $G$.  (For example, we cannot have $a = ab^2$ since then $1=b^2 $ and $b$ does not have order 3.)
The product $ba$ must be one of these six elements, and for elementary reasons it cannot be $1, a, b,$ or $b^2$. (For example, we cannot have $ba=b^2$ since then $a=b$ and we get that $a=b=1$.
If $ba=ab$ the group would be abelian, so the only choice remaining for $ba$ is  $ba=ab^2 = ab^{-1}$.
But there is only one group with $a^2=b^3= 1$ and $ba=ab^2$ because all the possible products of $a$ and $b$ are completely determined.  This is because in any such product we can commute the $a$'s leftward past the $b$'s by applying $ba = ab^2$, until we have something of the form $a^ib^j = a^{i\bmod 2}b^{j\bmod 3}$.  So $G$ the group is unique.
A: Suppose $G$ is a noneabelian group of order $6$. By Cauchy's theorem, there exists an element of order $2$, call it $b$, and an element of order $3$, call it $a$. The subgroup $H=\langle a\rangle$ is normal in $G$, since it has index $2$. Since $\langle a \rangle\cap\langle b\rangle =1$, $\langle a,b\rangle =G$. We have $bab^{-1}=a^i$, it cannot be $i=1$ since $G$ is nonabelian, and so $i=-1$. It follows $$G=\langle a,b\mid a^3,b^2,baba^{-1}\rangle$$
and so $G\simeq S_3$; or by $a\to (123)$, $b\to (12)$.
