Find $\mathrm{Aut}(G)$, $\mathrm{Inn}(G)$ and $\mathrm{Aut}(G)/\mathrm{Inn}(G)$ for $G = D_4$

We know that $$D_4=\langle x,y|x^2=y^4=1, (yx)^2=1\rangle = \{e, x, y, y^2, y^3, yx, y^2x, y^3x\}$$

Since $x^2 = 1 = (yx)^2 = (yxy)x$, we see that $x = yxy = y^2xy^2 = y^3xy^3 = y^nxy^n$. From this we can see that $|x| = |yx| = |y^2x|=|y^3x|=2$. Indeed:

$$(y^nx)^2=(y^nxy^n)x=x^2=1\;.$$

In fact, $2$ is the smallest positive integer $m$ such that $(y^nx)^m = 1$. On the other hand $|y^3|=4$. So if any automorphism is defined then, according to the Lemma you cited, it must preserve orders; so our possibilities are as follows:

One of

$$\begin{eqnarray} x&\to&x\\ x&\to&yx\\ x&\to&y^2x\\ x&\to&y^3x \end{eqnarray} $$

and one of

$$\begin{eqnarray} y&\to&y\\ y&\to&y^3 \end{eqnarray} $$

(Of course, in all cases $1\to 1$.)

To determine $\mathrm{Inn}(D_4)$,first observe that the complete list of inner automorphisms is $$\phi_{R_{0}},\phi_{R_{90}},\phi_{R_{180}},\phi_{R_{270}},\phi_{R_{H}},\phi_{R_{V}},\phi_{R_{D}},\phi_{R_{D'}}$$

Here $R_0,R_{90},R_{180},R_{270}$ are rotations of square. H and V denote the reflection of square with horizontal and vertical reflection and D and D' are denote diagonal reflection.Our job is to determine the no. of repetitions in this list.

Now u can check easily that $\phi_{R_{180}}=\phi_{R_{0}}$ also,$\phi_{R_{270}}=\phi_{R_{90}}$

similarly,$H=R_{180} V$ and $D'=R_{180} D$ so we have $\phi_{R_{H}}=\phi_{R_V}$ and $\phi_{R_D}=\phi_{R_D'}$

there are four inner automorphisms $$\mathrm{Inn}(D_4)=\{\phi_{R_0},\phi_{R_{90}},\phi_{R_H},\phi_{R_D}\}$$