An edge orientation procedure to generate all acyclic orientations of a graph

Question

Consider the following scheme for enumerating acyclic digraphs (DAGs) by orienting the edges in an undirected graph $G$ with $n = ||V||$ vertices:

(1) Generate all $n!$ possible permutations $p_i$ of the $n$ vertices in $G$.

(2) For each permutation $p_i = (v_a, v_b, ..., v_n)$, direct any unoriented edges adjacent to $v_a$ away from $v_a$, then direct any oriented edges adjacent to $v_b$ away from $v_b$ (if edges were previously oriented, and perhaps pointing towards $v_b$, leave those oriented edges unperturbed), and so on for all successive vertices in the permutation up to $v_n$.

(3) Check if the resulting acyclic digraph generated in step (2) is an existing element of some (initially empty) list $L$. If not, add it to the list.

Now my question is --- will $L$ contain all possible acyclic orientations of the initially undirected graph $G$, or might we miss some? If the latter is possible, can we say anything in particular about the nature of these missed acyclic digraphs?

(Just to be clear, by no means am I suggesting that the above procedure is an efficient way to generate sets of acyclic digraphs!)

Answer 1

The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation.

Every acyclic orientation of the graph induces at least one topological ordering of the vertices.

Every topological ordering of the vertices induces exactly one orientation of the graph (since if two distinct orientations were compatible with the ordering, they would differ in the orientation of at least one edge $(u,v)$ and hence $u$ would come both before and after $v$ in the permutation, which is a contradiction).

So the procedure generates all the acyclic orientations of the graph.