Determine the number of distinct labeling of $K_{r,r}$
In $G=K_{r,r}$, every vertices has degree $r$ so $|Aut(G)|=r$. I also know that the number of distinct labeling of $G$ of order $n$ is $\frac {n!}{|Aut(G)|}$
So the number of distinct labeling of $K_{r,r}$ is just $\frac {(2r)!}{r}$? This is unbelievably easy, so I doubt if it's correct.
The order of $Aut(G)$ is not $r$. There are $2(r!)$ automororphisms from $K_{r,r}$ to itself why? The only requisite for a bijection to be an automorphism is that pairs of vertices that where originally in the same part stay in the same part. Thus the number of ways to do it is $r!^2$. So the order of $Aut(G)$ is $r!^2$ and we conclude there are $\frac{(2r)!}{r!^2}$ labelings.
We can count the numbering of labelings directly, all you have to do to determine a label uniquely is pick one of the two parts of $K_{r,r}$ and select which labels the vertices in that part get. There are $\binom{2r}{r}=\frac{(2r)!}{r!^2}$ ways to do it.