Pancake Graphs and their recursive structure

A pancake graph has one vertex for every way to stack $n$ distinct pancakes: one vertex per permutation. Two stacks are adjacent when a single flip turns one into the other, where a flip means sliding a spatula under the top $k \ge 2$ pancakes and turning that block over.

Formally, let $S_n$ be the symmetric group on $n$ symbols. For $2 \le k \le n$ , the prefix reversal $r_k$ flips the first $k$ entries:

$r_k(a_1,a_2,\ldots,a_n)=(a_k,a_{k-1},\ldots,a_1,a_{k+1},\ldots,a_n).$

The pancake graph is the Cayley graph

$P_n = \operatorname{Cay}(S_n,\{r_2,r_3,\ldots,r_n\}).$

So $P_n$ has $n!$ vertices, and each vertex has one neighbor per available flip: degree $n-1$ for $n \ge 2$ .

Small Examples

Stack size	Vertices	Degree	Shape
$n=1$	$1$	$0$	A single vertex
$n=2$	$2$	$1$	A single edge
$n=3$	$6$	$2$	A 6-cycle
$n=4$	$24$	$3$	A 3-regular graph

In $P_4$ , the identity stack $1234$ has three neighbors, one per flip:

$1234 \stackrel{r_2}{\longleftrightarrow} 2134,\qquad 1234 \stackrel{r_3}{\longleftrightarrow} 3214,\qquad 1234 \stackrel{r_4}{\longleftrightarrow} 4321.$

The labels record which flip was used; the graph itself has just one undirected edge between each such pair.

$P_2$ : One Flip, One Edge

For two pancakes there are two stacks, $12$ and $21$ , and one flip, $r_2$ . So $P_2$ is a single edge.

The pancake graph P2 as a single edge

$P_3$ : A Hexagon

For three pancakes the only flips are $r_2$ and $r_3$ , so every vertex has degree two, and a connected 2-regular graph is a cycle. The six stacks form a hexagon, with the two flips alternating around it:

$123 \to 213 \to 312 \to 132 \to 231 \to 321 \to 123.$

The pancake graph P3 as a six-cycle

This is the best small example to keep in your head.

$P_4$ : The Full Graph

$P_4$ has $4! = 24$ vertices. Three flips are available ( $r_2$ , $r_3$ , $r_4$ ), so the graph is 3-regular, with

$\frac{24\cdot 3}{2}=36$

edges. Here is all of it. Gray edges are $r_2$ and $r_3$ flips; blue edges are $r_4$ flips. The four hexagons are not an accident of the layout — the next section explains them.

The full pancake graph P4 with all 24 vertices and 36 edges

The Recursive Structure

Group the stacks by the pancake on the bottom:

$V_i=\{\pi\in S_n : \pi_n=i\}.$

The flips $r_2,\ldots,r_{n-1}$ never touch the bottom pancake, so inside each $V_i$ they build a copy of $P_{n-1}$ . Only the full flip $r_n$ moves the bottom pancake. It pairs each stack with its complete reversal, so the $r_n$ edges form a perfect matching on $P_n$ , and every matching edge joins two different copies (a stack’s top and bottom pancakes differ).

In short: $P_n$ is $n$ copies of $P_{n-1}$ , glued together by a perfect matching.

This is exactly what the $P_4$ drawing above shows. The four hexagons are the copies of $P_3$ — the stacks sharing a bottom pancake — and the blue matching glues them together.

The glue also spreads out evenly. An $r_n$ edge joins $V_i$ to $V_j$ exactly when a stack has $i$ on the bottom and $j$ on top, and there are $(n-2)!$ ways to fill in the middle. So every pair of copies is joined by exactly $(n-2)!$ matching edges, and collapsing each copy to a single node turns $P_n$ into the complete graph $K_n$ .

For $P_4$ : four copies of $P_3$ , with $(4-2)!=2$ matching edges behind each dashed line.

Recursive decomposition of P4 into four copies of P3

For $P_5$ : five copies of $P_4$ , with $(5-2)!=6$ matching edges per pair.

Recursive decomposition of P5 into five copies of P4

For $P_6$ : six copies of $P_5$ , with $(6-2)!=24$ matching edges per pair.

Recursive decomposition of P6 into six copies of P5

This decomposition is the main reason pancake graphs are pleasant to prove things about: a question about $P_n$ usually reduces to the same question inside copies of $P_{n-1}$ , plus a controlled accounting of the matching edges. The companion note on Berge-Tutte obstructions and recursive cost shows that accounting in action.