= Solution
Choose the given <topological ordering>. Since $j$ precedes $k$, $j$ is not a descendant of $k$; since they are nonadjacent, it is not a parent of $k$. The <local Markov property of a directed acyclic graph> says that a node is d-separated from all its nondescendants other than its parents by its parent set. Therefore $j$ and $k$ are d-separated by $\operatorname{pa}(k)$.
It follows that adjacency of $Z_1,Z_2$ is certified by rejecting every null hypothesis
$$
Z_1\perp\!\!\!\perp Z_2\mid Z_S,
\qquad S\subseteq\{3,\ldots,p\}.
$$
If the vertices were nonadjacent, the theorem would supply one such separating parent set, whichever vertex comes later.
To certify that $X_1$ is a parent of $Y$, first reject
$$
X_1\perp\!\!\!\perp Y\mid (I,X_S)
$$
for every $S\subseteq\{2,\ldots,d\}$, which forces adjacency. Then reject
$$
I\perp\!\!\!\perp Y\mid X_S
$$
for every such $S$. If the adjacent edge were $Y\to X_1$, then $I\to X_1\leftarrow Y$ would orient $X_1$ as a collider, and the parent-set argument would provide a separator not containing $X_1$, contradicting the second collection of rejections. Hence the edge is $X_1\to Y$.
Solved by gpt-5.6-sol high.
Back to article page
