Covered edge reversal preserves d-separation

Put $P={\mathrm{pa}}_G(x)$, so ${\mathrm{pa}}_G(y)=P\cup \{x\}$. If reversing the arrow created a directed cycle, that cycle would use the new arrow $y\to x$, and the remaining part would be a directed path $x\to \cdots \to z\to y$ in $G$ with $z\mathrm{\ne }x$. Then $z\in P$, so $z\to x$ is also in $G$, making the directed cycle $x\to \cdots \to z\to x$ in $G$, a contradiction. Thus $G^{\mathrm{\prime }}$ is acyclic.

The full moral graphs of $G$ and $G^{\mathrm{\prime }}$ coincide. Their skeletons coincide. The only changed parent sets are ${\mathrm{pa}}_G(x)=P$, ${\mathrm{pa}}_G(y)=P\cup \{x\}$ and ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(x)=P\cup \{y\}$, ${\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)=P$. Any pair newly married at $y$ in $G$ or at $x$ in $G^{\mathrm{\prime }}$ already belongs to the clique on $P\cup \{x,y\}$: pairs involving $x$ or $y$ are skeleton edges, and pairs in $P$ are married at both $x$ and $y$. All other parent sets are unchanged, so the moral edge sets are identical.

Fix pairwise disjoint query sets $A,B,S$ and put $T=A\cup B\cup S$. The ancestor sets of $T$ in $G$ and $G^{\mathrm{\prime }}$ differ, if at all, only by $x$ or $y$. Indeed, a directed path whose existence changes must use the reversed edge. A path in $G$ that uses $x\to y$ and starts at $v\mathrm{\ne }x$ enters $x$ from some $p\in P$; in $G^{\mathrm{\prime }}$ replace $p\to x\to y$ by the unchanged arrow $p\to y$. Therefore only $x$ can cease to be an ancestor. Symmetrically, a path in $G^{\mathrm{\prime }}$ using $y\to x$ and starting at $v\mathrm{\ne }y$ enters $y$ from $p\in P={\mathrm{pa}}_{G^{\mathrm{\prime }}}(y)$; in $G$ replace $p\to y\to x$ by $p\to x$. Therefore only $y$ can become an ancestor. If $x$ is lost, $y$ belongs to both ancestor sets; if $y$ is gained, $x$ belongs to both.

If the ancestor sets are equal, step 1.2 shows the induced ancestral moral graphs are equal. Suppose instead that $x$ is an ancestor only in $G$. Then $x\mathrm{\notin }T$ and $y$ is a common ancestor of $T$. In the moral graph induced on ${\mathrm{An}}_G(T)$, every neighbor of $x$ is in $P\cup \{y\}$: its parents lie in $P$; among its children only $y$ can be ancestral, since any other child has an unchanged arrow from $x$ and would make $x$ an ancestor in $G^{\mathrm{\prime }}$; and a marriage through a child other than $y$ would have the same consequence, while a marriage through $y$ uses another parent in $P$. The vertices in $P\cup \{y\}$ form a clique because they are parents of $y$ in $G$. Hence $x$ is simplicial in the ancestral moral graph. The case that $y$ is gained only in $G^{\mathrm{\prime }}$ is symmetric, with its neighbors contained in the clique $P\cup \{x\}$.

Removing an unconditioned simplicial vertex does not change separation between $A$ and $B$ after deleting $S$: the vertex is not in $T$, and any path through it can be shortened by replacing its two incident edges with the edge joining its neighbors, which exists because the neighborhood is a clique. Conversely, every path in the smaller graph remains in the larger graph. Thus the two ancestral moral graphs separate $A$ and $B$ by $S$ in exactly the same cases. By [F1], $G$ and $G^{\mathrm{\prime }}$ have the same d-separation relations.