[proofplan]
The Markov and faithfulness assumptions identify the observed conditional independence model with the d-separation model of the true DAG $G$. The [Verma-Pearl Markov equivalence characterization](/theorems/9691) then says that this independence model determines exactly the Markov equivalence class of $G$. Finally, the CPDAG records precisely which edge orientations are common to every DAG in that equivalence class, so directed CPDAG edges are identifiable and undirected CPDAG edges are not.
[/proofplan]
[step:Identify the observational independence model with the graphical model of $G$]
Define the observational conditional independence model
\begin{align*}
\mathcal I(P):=\{(A,B,C): A,B,C\subset V \text{ are pairwise disjoint and } X_A \perp\!\!\!\perp X_B \mid X_C \text{ under } P\}.
\end{align*}
Define the graphical d-separation model of $G$ by
\begin{align*}
\mathcal I(G):=\{(A,B,C): A,B,C\subset V \text{ are pairwise disjoint and } A \text{ is d-separated from } B \text{ by } C \text{ in } G\}.
\end{align*}
By the assumed Markov and faithfulness conditions, for every pairwise disjoint triple $A,B,C\subset V$,
\begin{align*}
(A,B,C)\in \mathcal I(P) \iff (A,B,C)\in \mathcal I(G).
\end{align*}
Hence
\begin{align*}
\mathcal I(P)=\mathcal I(G).
\end{align*}
[guided]
The first point is to translate the statistical information into graph-theoretic information. Define
\begin{align*}
\mathcal I(P):=\{(A,B,C): A,B,C\subset V \text{ are pairwise disjoint and } X_A \perp\!\!\!\perp X_B \mid X_C \text{ under } P\}.
\end{align*}
This is exactly the data the theorem allows us to use: the complete list of observational conditional independences.
Now define the corresponding graphical independence model of the DAG $G$:
\begin{align*}
\mathcal I(G):=\{(A,B,C): A,B,C\subset V \text{ are pairwise disjoint and } A \text{ is d-separated from } B \text{ by } C \text{ in } G\}.
\end{align*}
The Markov assumption gives one implication:
\begin{align*}
(A,B,C)\in \mathcal I(G) \implies (A,B,C)\in \mathcal I(P).
\end{align*}
Faithfulness gives the converse:
\begin{align*}
(A,B,C)\in \mathcal I(P) \implies (A,B,C)\in \mathcal I(G).
\end{align*}
Therefore, for every pairwise disjoint triple $A,B,C\subset V$,
\begin{align*}
(A,B,C)\in \mathcal I(P) \iff (A,B,C)\in \mathcal I(G).
\end{align*}
Thus the complete observational conditional independence model is not merely compatible with $G$; it is exactly the d-separation model of $G$:
\begin{align*}
\mathcal I(P)=\mathcal I(G).
\end{align*}
This is where Markovness and faithfulness are used. Without faithfulness, some graphical dependences could disappear accidentally in $P$, and without Markovness, some graphical separations might fail to appear as statistical conditional independences.
[/guided]
[/step]
[step:Use Verma-Pearl to recover the Markov equivalence class]
Let $\mathcal M(G)$ denote the Markov equivalence class of $G$, meaning the set of all directed acyclic graphs $H$ on vertex set $V$ such that
\begin{align*}
\mathcal I(H)=\mathcal I(G).
\end{align*}
By [citetheorem:9691], two directed acyclic graphs on $V$ have the same d-separation model exactly when they have the same skeleton and the same unshielded colliders. Hence the model $\mathcal I(G)$ determines $\mathcal M(G)$. Since $\mathcal I(P)=\mathcal I(G)$, the complete observational conditional independence model $\mathcal I(P)$ determines precisely the class $\mathcal M(G)$.
[/step]
[step:Read compelled orientations from the CPDAG]
Let $C:=\operatorname{CPDAG}(G)$ be the completed partially directed acyclic graph representing $\mathcal M(G)$. By the defining semantics of a CPDAG, an adjacency $u,v\in V$ is oriented as $u\to v$ in $C$ if and only if every DAG $H\in\mathcal M(G)$ contains the directed edge $u\to v$. Likewise, the edge between $u$ and $v$ is undirected in $C$ if and only if the orientation of that adjacency is not compelled in $\mathcal M(G)$, equivalently there exist DAGs $H_1,H_2\in\mathcal M(G)$ such that $H_1$ contains $u\to v$ and $H_2$ contains $v\to u$.
[/step]
[step:Prove that directed CPDAG edges are identifiable]
Assume that $C$ contains the directed edge $u\to v$. Let $H$ be any directed acyclic graph on $V$ whose complete conditional independence model agrees with the observational model:
\begin{align*}
\mathcal I(H)=\mathcal I(P).
\end{align*}
Since $\mathcal I(P)=\mathcal I(G)$, this gives
\begin{align*}
\mathcal I(H)=\mathcal I(G).
\end{align*}
Therefore $H\in\mathcal M(G)$. Because $u\to v$ is directed in $C$, the CPDAG semantics imply that every DAG in $\mathcal M(G)$ contains $u\to v$. In particular, $H$ contains $u\to v$. Since $H$ was arbitrary among all DAGs with conditional independence model $\mathcal I(P)$, the direction $u\to v$ is identifiable from $\mathcal I(P)$.
[/step]
[step:Prove that undirected CPDAG edges are not identifiable]
Assume conversely that the adjacency between $u$ and $v$ is not directed as $u\to v$ in $C$. If the edge is directed as $v\to u$ in $C$, then every DAG in $\mathcal M(G)$ contains $v\to u$, so the direction $u\to v$ is not the identifiable direction. If the edge is undirected in $C$, the CPDAG semantics give DAGs $H_1,H_2\in\mathcal M(G)$ such that $H_1$ contains $u\to v$ and $H_2$ contains $v\to u$.
For these two DAGs,
\begin{align*}
\mathcal I(H_1)=\mathcal I(G)=\mathcal I(P)
\end{align*}
and
\begin{align*}
\mathcal I(H_2)=\mathcal I(G)=\mathcal I(P).
\end{align*}
Thus $H_1$ and $H_2$ are observationally indistinguishable from the complete conditional independence model, while they orient the same adjacency in opposite directions. Therefore $\mathcal I(P)$ cannot identify $u\to v$ in the sense of forcing that orientation across all compatible DAGs.
Combining the directed and undirected cases, an edge direction is identifiable from the complete observational conditional independence model if and only if it is directed in $\operatorname{CPDAG}(G)$.
[/step]
