The vertices of the $G_n$ permutation graph are labeled with permutations of the $n$-element set. The two vertices in this graph are connected by an edge if the corresponding permutations differ in the transposition of adjacent elements. For example when we have two vertex $1,2,4,3$ and $1,2,3,4$ then are connected.
For which $n$ is $G_n$ graph planar? Justify the answer
$G_n$ - vertices are permutations $\left\{ 1,2,...,n \right\} $
For example $n=4$: $\left\{ 1,2,3,4 \right\}$ 
Definitely for $n-2>5 \Rightarrow n>7$ is not planar because we have a claim that every planar graph have a vertex for which: $\deg(v) \le 5$.
For $n=1,2,3$ is a planar.
In the planar graph we have:
$$m \le 3n-6$$
$$\frac{(n-1)!(n-2)}{2} \le 3(n-2)$$
$$(n-1)! \le 6$$
$$(n-1)\le 3$$
$$n \le 4$$
The question remains what for $n = 4$ $\rightarrow $ graph is a planar because we draw it.
So $n \in \left\{ 1,2,3,4 \right\}$
However, I need a person who check this solution.
The graph $G_n$ has $n!$ vertices, so the inequality $M \le 3N-6$ (where I wrote $M, N$ in capital letters to avoid confusion) should tell us that $$\frac{n! (n-1)}{2} \le 3n! - 6$$ and not $3n - 6$. This is true for $n=6$, since $\frac{6! (6-1)}{2} = 1800 \le 3 \cdot 720 - 6 = 2154$, but false for $n=7$, so it's not an improvement on the previous bound.
(This isn't surprising, since we prove that every planar graph has a vertex of degree at most $5$ by showing that the average degree satisfies $\frac{2M}{N} \le \frac{2(3N-6)}{N} = 6 - \frac{12}{N} < 6$, using the same inequality as a starting point.)
However, $G_n$ is bipartite: if we classify the permutations into even and odd permutations, then each edge joins an even permutation to an odd one. So the stronger inequality $M \le 2N - 4$ holds for $G_n$.
(We prove this inequality in a similar way, starting from Euler's formula $N - M + P = 2$, where $P$ is the number of faces. For a bipartite graph, every face has at least $4$ edges, so we have $2M \ge 4P$, or $M \ge 2P$, and therefore $M \ge 2(M-N+2)$. This simplifies to $M \le 2N-4$.)
From the inequality $M \le 2N - 4$, we get $\frac{2M}{N} \le 4 - \frac 8N < 4$, so the average degree in a planar bipartite graph is less than $4$, and therefore every such graph has a vertex of degree $3$ or less. Every vertex in $G_n$ has degree $n-1$, so the graph cannot be planar for $n \ge 5$.
For completeness, and because I like pictures, here is a planar drawing of $G_4$:
(The graph $G_4$ is in fact the skeleton graph of the truncated cuboctahedron.)