DAG Markov equivalence is determined by skeletons and unshielded colliders

First assume that $G_1,G_2$ have the same skeleton and the same unshielded colliders. A finite DAG has a topological order: if every remaining vertex had an incoming arrow, following incoming arrows in the finite graph would repeat a vertex and create a directed cycle; remove a source and repeat. Fix such an order $\prec$ for $G_1$. If the DAGs differ, choose the $\prec$-earliest vertex $\beta$ with ${\mathrm{pa}}_{G_1}(\beta )\setminus {\mathrm{pa}}_{G_2}(\beta )\mathrm{\ne }\mathrm{\varnothing }$, and choose the $\prec$-latest $\alpha$ in that difference. Then $\alpha \to \beta$ occurs in $G_1$ and $\beta \to \alpha$ in $G_2$.

Conversely, assume $G_1,G_2$ are Markov equivalent. If their skeletons differed, [F2] would give a pair separated in one graph but not the other. Thus their skeletons agree. If an unshielded collider $i\to k\leftarrow j$ occurred in $G_1$ but not in $G_2$, then $i,j$ are nonadjacent in both. By [F2] choose $S$ that d-separates $i,j$ in $G_1$. The path $i\to k\leftarrow j$ shows that no descendant of $k$, including $k$, can lie in $S$, because otherwise that path would be active. In $G_2$, the same unshielded triple has a noncollider at $k$; since $k\mathrm{\notin }S$, the two-edge path is active, so $S$ does not d-separate $i,j$ there. This contradicts Markov equivalence. Interchanging $G_1,G_2$ rules out a collider present only in $G_2$.

Let $\gamma \mathrm{\ne }\alpha$ be another parent of $\beta$ in $G_1$. If $\gamma$ were not a parent of $\alpha$, then either $\gamma$ and $\alpha$ would be nonadjacent, making $\alpha \to \beta \leftarrow \gamma$ an unshielded collider absent from $G_2$, or they would be adjacent with $\alpha \to \gamma$ in $G_1$. The first case contradicts equality of colliders; in the second case, $G_2$ cannot retain both $\alpha \to \gamma$ and $\gamma \to \beta$, because together with $\beta \to \alpha$ they form a directed cycle. If $\alpha \to \gamma$ is reversed in $G_2$, then $\gamma \prec \beta$ is an earlier vertex with a differing parent; if $\gamma \to \beta$ is reversed, then $\gamma$ is a later member than $\alpha$ of ${\mathrm{pa}}_{G_1}(\beta )\setminus {\mathrm{pa}}_{G_2}(\beta )$. Both contradict the choices in step 1.1. Hence every parent of $\beta$ other than $\alpha$ is a parent of $\alpha$.

To prove ${\mathrm{pa}}_{G_1}(\alpha )\subseteq {\mathrm{pa}}_{G_1}(\beta )$, suppose instead that $\gamma \to \alpha$ in $G_1$ but $\gamma \mathrm{\notin }{\mathrm{pa}}_{G_1}(\beta )$. Minimality of $\beta$ implies $\gamma \to \alpha$ is also present in $G_2$; otherwise the earlier vertex $\alpha$ would already have a differing parent. If $\gamma$ were not adjacent to $\beta$, then $G_2$ would contain the unshielded collider $\beta \to \alpha \leftarrow \gamma$, while $G_1$ has the noncollider chain $\gamma \to \alpha \to \beta$, contradicting equality of colliders. Thus $\gamma$ is adjacent to $\beta$. In $G_1$ it must be oriented $\gamma \to \beta$, since $\beta \to \gamma$ would make a directed cycle with $\gamma \to \alpha \to \beta$. This contradicts the assumption that $\gamma$ is not a parent of $\beta$. Therefore the inclusion holds. Together with step 2.1, ${\mathrm{pa}}_{G_1}(\beta )={\mathrm{pa}}_{G_1}(\alpha )\cup \{\alpha \}$, so $\alpha \to \beta$ is covered.

Reverse this covered arrow in $G_1$. By [F3] the result remains a DAG and is Markov equivalent to $G_1$. It has the same skeleton, and it has the same unshielded colliders: an edge in an unshielded collider cannot be covered, because the other parent of the collider would then also be a parent of the edge's tail and hence adjacent to it. Exactly one edge now agrees with $G_2$, so the finite number of edge-orientation disagreements decreases by one. If any disagreement remains, choose the earliest differing parent set again; the argument in steps 1.1–3.1 applies because the skeleton and collider set are unchanged. Thus finitely many covered reversals transform $G_1$ into $G_2$, and each reversal preserves d-separation.

The two directions prove the equivalence.