Edges of a permutohedron Consider a permutohedron $P_n$ (this is a polytope which is  a convex hull of $n!$ points, which are obtained from $(1,2,...,n)$ by all possible permutations of coordinates). 
I have to prove the following: 2 vertices are connected with an edge iff their coordinates differ by transposition of 2 numbers which differ by 1.
I have managed to prove only one side (if they differ in such way then they are connected with an edge). Please help.
 A: Recall that a face of $P\subset\Bbb R^n$ is defined by a set of vertices $v_1,...,v_k\in \mathrm{vert}(P)$ that maximize a linear functional $\langle c,\cdot\rangle$ for some $c\in\Bbb R^n$.
Now, given a $c\in\Bbb R^n$ it is not hard to characterize the vertices of the permutahedron $P$ that maximize the functional $\langle c,\cdot\rangle$.
Let me write $v(i)$ for the index of the component at which $i\in\{1,...,n\}$ occurs in $v\in\mathrm{vert}(P)$ (this is well-defined for the vertices of the permutahedron).
Then, a vertex $v\in\mathrm{vert}(P)$ maximizes $\langle c,\cdot\rangle$ if and only if
$$ c_{v(1)} \le \cdots \le c_{v(n)},$$
where $c_i$ denotes the $i$-th component of $c$. If this is not clear to you, write down $\langle c,v\rangle$ in components $c_1v_1+\cdots + c_n v_n$ and observe that above characterization ensures that the largest component of $c$ is paired with the largest component of $v$, and the second-largest component  of $c$ is paired with the second-largest component of $v$, and so on. And this is the way to obtain the largest possible inner product.
For example, if $c$ has all different components, then above sorted sequence is unique (given by sorting $c$), and there is only a single vertex that maximizes $\langle c,\cdot\rangle$. To define an edge, we need exactly two ways to sort $c$ in non-decreasing order.
This can be done by making exactly two components of $c$ equal (convince yourself, that this is the only way).
Let's say, the identical components are $c_k$ and $c_\ell$. Then, we can sort them in the two ways
$$...\le c_k\le c_\ell\le...\qquad\text{or}\qquad ...\le c_\ell\le c_k\le ...$$
Hence, these identical components occupy consecutive positions in the sorted sequence, let's say positions $i$ and $i+1$. The only two vertices that maximize $\langle c,\cdot\rangle$ have then determined positions for all entries other than $i$ and $i+1$, and
$$v(i)=k,\; v(i+1)=\ell\qquad\text{and}\qquad \bar v(i)=\ell,\; \bar v(i+1)=k.$$
This means, that $v$ has consecutive numbers at index $k$ and $\ell$, and these numbers appear swapped in the other vertex $\bar v$.
