Every non abelian group of order 6 is isomorphic to $\displaystyle S_{3}$ (the symmetry group of order 6). Every non abelian group of order $6$ is isomorphic to $\displaystyle S_{3}$ (the symmetry group of order $6$).
I tried to prove it but got stuck mid-way.
Let $\displaystyle G$ be a non-abelian group of order $6$. In $\displaystyle G,$ not all elements (non-identity) have order 2 because then the group would be abelian ($\displaystyle \forall \ a,b\in G\Longrightarrow ( ab) =( ab)^{-1} \Longrightarrow ab=ba)$.
Similarly, not all non identity elements can have order $3$ (order $3$ groups come in multiples of $2$).
We conclude there is at least one element $\displaystyle a_{1} \in G$ of order $3$ and one element $\displaystyle b_{1} \in G$ of order $2$. We have now two cases:
Case 1: $\displaystyle G$ has two order $3$ elements and three order $2$ elements.
$\displaystyle S_{3}$ also has three order $2$ elements (viz. the cycles $\displaystyle ( 12) ,( 23) ,( 31)$) and two order 3 elements (viz. the cycles $\displaystyle \left(( 123) ,( 123)^{-1}\right)$.
$\displaystyle G=\{e,a_{1} ,a_{1}^{-1} ,b_{1} ,b_{2} ,b_{3} \}$.  $\displaystyle \phi :\ G\rightarrow S_{3}$ defined by $\displaystyle \phi ( e) =( 1) ,\ \phi ( a_{1}) =( 123) ,\phi \left( a_{1}^{-1}\right) =( 132) ,\ \phi ( b_{1}) =( 12) ,\phi ( b_{2}) =( 23)$ and $\displaystyle \phi ( b_{3}) =( 31)$ is an isomorphism. So $\displaystyle G\cong \ S_{3}$.
Case 2: $\displaystyle G$ has four order 3 elements and one order 2 element.
This is where I am not getting any contradiction (unless I'm trying to prove a wrong statement).
$\displaystyle G=\{e,a_{1} ,a_{1}^{-1} ,a_{2} ,a_{2}^{-1} ,b\}$. Now $\displaystyle ba_{1} \notin \{e,a_{1} ,b,a_{1}^{-1} \}$.
So we have two cases:Either $\displaystyle ba_{1} =a_{2}$ or $\displaystyle ba_{1} =a_{2}^{-1}$
If $\displaystyle ba_{1} =a_{2}$ then $\displaystyle b=a_{2} a_{1}^{2} =a_{1}^{-2} a_{2}^{-1} =a_{1} a_{2}^{-1} \Longrightarrow a_{2} a_{1}^{-1} =a_{1} a_{2}^{-1}$
How does this give any contradiction? Thanks.
PS: I am not allowed to use group actions or Sylow's theorems.
 A: Let us get a contradiction in Case 2:
Suppose there are four distinct elements of order $3$. Then, they are of the form $a, a^2, b, b^2$ with $a^2 = a^{-1}$ and $b^2 = b^{-1}$. Let $c$ be the unique element of order $2$.
Consider the element $ab$. What are its possible orders? Clearly, $1$ and $6$ are not possible. What about $2$?
Well, if $ab$ has order $2$, then $ab = c$. Note that the coset $a \cdot \{1, b, b^2\}$ is equal to $G \setminus \{1, b, b^2\} = \{c, a, a^2\}$. Thus, we see that $ab^2 = a^2$.
Now, cancelling $a$ gives $b^2 = a$, which is a contradiction since $a$ and $b^2$ were distinct.
Thus, $ab$ has order $3$. But the only elements of order $3$ are $a, a^2, b, b^2$. Equating $ab$ to each of them and cancelling appropriately gives a contradiction.

As pointed out in the comments, your solution of Case 1 is not complete.
A: You're almost there. By Lagrange's theorem, you noted that possible orders of elements are $1$ (only the neutral element), $2$, $3$ and $6$, where the last possibility is excluded, as it would imply that $G$ is abelian. Then by a combinatorial argument, you showed that there's an element $a$ of order $3$ and an element $b$ of order $2$.
Now consider the sets $A := \{ 1,a,a^2 \}$ and $bA := \{ b,ba,ba^2 \}$. As pointed out by Aryaman Maithani, together they give the whole group $G$. Let me elaborate on this:

*

*Note that $A$ consists of $3$ different elements (quite trivially) and $bA$ does too (check for yourself what happens if, say, $ba = ba^2$).

*Any element of $A$ is different than any element of $bA$ (again, see what would follow from e.g. $a = ba^2$).

It follows that $A$ and $bA$ together have $6$ elements, so they form the whole group. The same reasoning can be also applied to the set $Ab = \{ b,ab,a^2b \}$, showing that $bA = Ab$ (both are complements of $A$!)

Two side remarks are in order:
Remark 1. In a similar fashion, if $G$ is a finite group and $A \leqslant G$ its subgroup, then two cosets $g_1A$, $g_2 A$ (for any
$g_1,g_2 \in G$) are either identical or disjoint. This basic
observation lies behind Lagrange's theorem you used - the order
of any element divides the order of the group.
Remark 2. Our reasoning actually shows that if $A \leqslant G$ is a subsgroup and $|G| = 2|A|$ (i.e., $A$ is of index $2$), then
$gA=Ag$ for any $g \in G$ (i.e., $A$ is normal). This fact is
sometimes useful.

Returning to our specific case, we know now that $\{ b, ba, ba^2 \} = \{ b, ab, ab^2 \}$. Clearly, there are two cases:

*

*If $ba=ab$, then we look at the order of this element. Since $(ab)^k=a^kb^k$ (as the elements $a$ and $b$ commute), we see that $(ab)^2 = a^2 \neq 1$ and $(ab)^3 = b^3 \neq 1$. This implies that $ab$ has order $6$ and $G$ is abelian - a contradiction.

*If $ba=a^2b$ and $ba^2=ab$, the whole structure of $G$ is uniquely determined. See for yourself! For example:
$$
ba^2 \cdot ba 
= b \cdot a^2 b \cdot a 
= b \cdot ba \cdot a 
= a^2.
$$
Similarly, one can transform any product $b^{i_1} a^{j_1} \cdot b^{i_2} a^{j_2}$ into the form $b^{i}a^{j}$ again (where $i=0,1$, $j=0,1,2$).

This tells us that there is (up to isomorphism) at least one non-abelian group of order $6$, and since there is one ($S_3$), it must be it. Or in other words, take $a' := (123)$, $b' := (12)$ and then
$$
\phi \colon G \to S_3, \quad 
\phi(a) := a', \ \phi(b) := b', \ \phi(ba) := b'a'
\quad \text{and so on.}
$$
Our previous reasoning shows that this must be an isomorphism.

One final remark:
Remark 3. It's not very hard to exclude Case 2, i.e., show that there are two elements of order $3$ and three elements of order $2$,
just as in $S_3$. However, a priori these elements could behave in
different ways, so it's not clear that the map $\phi$ above (or a
similarly constructed map) is well-defined and homomorphic.

A: Alternatiuve approach using as little group theory as possible: Note that in order to have a non-abelian group, there must exist elements $a,b$ with $ab\ne ba$. With $c:=ab$ and $d:=ba$, we already know five distinct elements: $1,a,b,c,d$. Indeed, we must have $a\ne 1$ becase $1$ commutes with everything. Similarly, $b\ne 1$. Hence $c\ne a$, $c\ne b$, $d\ne a$, $d\ne b$. Of course, $b\ne a$ and $b\ne a^{-1}$ as these would commute. Thus also $c\ne1$ and $d\ne 1$.
Let $g$ be the sixth element. What about $a^{-1}$? We saw that it is not $b$. Nor can it be $1$ as $a\ne 1$. It cannot be $c$ or $d$ as that would make $b=a^{-2}$ and commute with $a$. Thus $a^{-1}=a$ or $a^{-1}=g$. By the same reasoning, $b^{-1}=b$ or $b^{-1}=g$. We cannot have $a^{-1}=g=b^{-1}$, hence one of $a,b$ is its own inverse, wlog. $a^{-1}=a$, i.e., $a^2=1$.
There are two cases: $b^2=1$ or $b^2=g$. In the first case, we have so far the following multiplication table
$$\begin{matrix}*&|&a&b&c&d&g\\\hline
a&|&1&c&b&?&?\\
b&|&d&1&?&a&?\\
c&|&?&a&?&1&?\\
d&|&b&?&1&?&?\\
g&|&?&?&?&?&?
\end{matrix} $$
Using "Sudoko skills" - every row must a fixpoint free permutation, in particular, $g$ must not appear in the last column/row - we readily the table:
$$\begin{matrix}*&|&a&b&c&d&g\\\hline
a&|&1&c&b&g&d\\
b&|&d&1&g&a&c\\
c&|&g&a&d&1&b\\
d&|&b&g&1&c&a\\
g&|&c&d&a&b&1
\end{matrix} $$
and also readily recognize this as isomorphic to $S_3$.
In the second case, our unsolved "sudoku" looks like
$$\begin{matrix}*&|&a&b&c&d&g\\\hline
a&|&1&c&b&?&?\\
b&|&d&g&?&?&?\\
c&|&?&?&?&?&?\\
d&|&b&?&g&?&?\\
g&|&?&?&?&?&?
\end{matrix} $$
and can be partially completed to
$$\begin{matrix}*&|&a&b&c&d&g\\\hline
a&|&1&c&b&g&d\\
b&|&d&g&?&c&?\\
c&|&g&d&?&b&?\\
d&|&b&?&g&?&?\\
g&|&c&?&d&?&?
\end{matrix} $$
If we assume that $c^2,d^2,g^2$ are all $\ne 1$, we conclude that $cg=1$ and that $gd=1$, so $c=g^{-1}=d$, contradiction. Hence one of $c^2,d^2,g^2$ is $=1$. As $c,d,g$ do not commute with $a$, this allows us to reduce to the first case.
A: Given that $S_3\cong D_3$, the dihedral group of order six, we can use the following

Theorem: Let $G$ be a group of order $2p$, where $p$ is a prime greater than $2$. Then $G$ is isomorphic to $\Bbb Z_{2p}$ or $D_p.$

For a proof, see Theorem 7.3 of Gallian's "Contemporary Abstract Algebra (Eighth Edition)".
