Pancake Sorting Graph Recursive Definition
From Wikipedia: 


  The pancake graph $P_n$ or $n$-pancake graph is a graph whose vertices
  are the permutations of $n$ symbols from 1 to $n$ and its edges are given
  between permutations transitive by prefix reversals.


$P_n$ can be constructed from $n$ copies of $P_{n-1}$. We can construct $P_4$ from $P_3$, which looks like: 

 

We start by making 4 copies of $P_3$ and numbering them 1 through $n$. Let's look at one particular copy and call it copy $i$. For each node in that instance of $P_{n-1}$, replace $i$ with $n$ and then append $i$ to the end of each sequence. For the $n$th copy, we don't have to do any replacing and can simply append $n$ to the end. 

For example, for the 2nd copy of $P_3$ we'll first replace all the 2s with 4s and then append 2 to the end: 



We now have a graph with nodes for all of the permutations of the elements from 1 to 4, and we have edges between sequences that can be transformed into one another by flipping a proper prefix. Edges from $P_{n-1}$ are still valid in $P_n$ because the only thing we've done is relabel and append a suffix.

Now go through each node and add a new edge going to the node corresponding to flipping the entire sequence. For example, (4,3,1,2) gets connected to (2,1,3,4), (1,2,3,4) gets connected to (4,3,2,1), etc. 

The final graph for $P_4$ as shown in the Wikipedia article linked in the question looks like: