Why is the permutohedron simple?

By @anomaly's comment, you only need to count the edges at any one vertex. Notice further that the projection which simply drops the $n$th coordinate is injective and dimension-preserving on the vertices of the permutahedron, so the convex hull in the first $n-1$ dimensions has the same combinatorial structure as the original permutahedron. In this structure, the set of points with greatest ($n-1$)st coordinate is clearly both (a) on the convex hull and (b) a copy of the order $n-1$ permutahedron. So by induction each vertex of it has $n-2$ edges in that same layer; we just have to find at least one vertex of it that has only a single edge in which the ($n-1$)st coordinate changes. But in particular, looking along the $n-1$st coordinate, the vertices which consist of all permutations of (1,2,...,$n-2$) followed by $n$ lie directly "above" the same permutation of (1,2,...,$n-2$) followed by $n-1$, so they must each have a single additional edge in the overall convex hull, parallel to the $n-1$st axis. This completes the proof.