[proofplan] The proof separates the correctness of PC into its three algorithmic phases. Markovness and faithfulness first identify the population oracle answers exactly with d-separation statements in the true DAG. The skeleton phase is then correct because non-adjacent pairs are removed by a valid separating set while adjacent pairs are never d-separated by variables excluding the endpoints. The unshielded-collider phase recovers exactly the true v-structures, and the Verma-Pearl characterization plus completeness of the Meek rules identifies the final mixed graph with the CPDAG of the Markov equivalence class of $G$. [/proofplan] [step:Translate every oracle answer into a d-separation statement in $G$] For pairwise disjoint subsets $A,B,C\subset V$, define the oracle predicate \begin{align*} \mathcal O(A,B,C)=1 \quad \text{if and only if} \quad X_A \perp\!\!\!\perp X_B \mid X_C \text{ under } P. \end{align*} By the Markov and faithfulness assumptions, for every such triple $(A,B,C)$, \begin{align*} \mathcal O(A,B,C)=1 \quad \text{if and only if} \quad A \text{ and } B \text{ are d-separated by } C \text{ in } G. \end{align*} Thus the population PC algorithm, although phrased in terms of conditional independence under $P$, makes exactly the same yes/no decisions as the corresponding d-separation oracle for $G$. [/step] [step:Recover the skeleton of $G$ during the deletion phase] Let $H_0$ denote the complete undirected graph on $V$. During the skeleton phase, every set $S\subset V\setminus\{u,v\}$ is an admissible candidate for separating $u$ and $v$. The population PC algorithm deletes an undirected edge $\{u,v\}$ when it finds such a set with $\mathcal O(\{u\},\{v\},S)=1$, and it records one such set as $\operatorname{Sep}(u,v)$. We first justify the adjacency characterization for DAGs. If $u$ and $v$ are adjacent in $G$, then the one-edge path between $u$ and $v$ has no interior vertex, so no conditioning set $S\subset V\setminus\{u,v\}$ blocks that path. Hence $u$ and $v$ are not d-separated by any such $S$. Conversely, suppose $u$ and $v$ are not adjacent in $G$. Define \begin{align*} S:=\operatorname{An}_G(\{u,v\})\setminus\{u,v\}, \end{align*} where $\operatorname{An}_G(\{u,v\})$ is the set of vertices with a directed path to $u$ or to $v$, with paths of length zero allowed. Then $S\subset V\setminus\{u,v\}$. Apply the [[Moralized Ancestral Graph Criterion](/theorems/9670)][citetheorem:9670] with $A=\{u\}$, $B=\{v\}$, and $Z=S$. The relevant ancestral set is $W=\operatorname{An}_G(\{u,v\}\cup S)=\{u,v\}\cup S$. In the moral graph of the induced sub-DAG on $W$, the vertices $u$ and $v$ are not adjacent: they are not adjacent in $G$ by assumption, and they cannot acquire a moral edge through a common child $w\in W$, because $u\to w\leftarrow v$ together with $w\in\operatorname{An}_G(\{u,v\})$ would create a directed cycle in $G$. After removing $S$, only $u$ and $v$ remain, with no edge between them. Thus $S$ separates $u$ and $v$ in the moralized ancestral graph, and the criterion gives that $S$ d-separates $u$ and $v$ in $G$. Therefore vertices $u,v\in V$ are adjacent in $G$ if and only if no subset $S\subset V\setminus\{u,v\}$ d-separates $u$ and $v$ in $G$. Therefore, if $u$ and $v$ are adjacent in $G$, the oracle never returns conditional independence for any admissible conditioning set $S$, and the edge $\{u,v\}$ is never deleted. Conversely, suppose $u$ and $v$ are not adjacent in $G$. By the adjacency characterization, choose a separating set $S\subset V\setminus\{u,v\}$ such that $u$ and $v$ are d-separated by $S$ in $G$. The skeleton-deletion phase in the stated population PC procedure treats every subset of $V\setminus\{u,v\}$ as an admissible candidate and is exhaustive, so it tests an oracle-positive separating set before termination whenever one exists. By the oracle-d-separation equivalence from the previous step, $\mathcal O(\{u\},\{v\},S)=1$, so the algorithm deletes $\{u,v\}$. Hence the undirected graph left after the skeleton phase has edge set exactly the skeleton of $G$. [guided] The skeleton phase starts from too many edges: $H_0$ is the complete undirected graph on $V$. Its task is only deletion. For two distinct vertices $u,v\in V$, the algorithm is allowed to delete $\{u,v\}$ only after finding a conditioning set $S\subset V\setminus\{u,v\}$ for which the population oracle reports \begin{align*} \mathcal O(\{u\},\{v\},S)=1. \end{align*} By the first step, this oracle answer is equivalent to the graphical statement that $u$ and $v$ are d-separated by $S$ in the true DAG $G$. Now fix adjacent vertices $u$ and $v$ in $G$. Why can no conditioning set delete this true edge? The path consisting of the single edge between $u$ and $v$ has no interior vertices. A path is blocked only through conditions on interior non-colliders or interior colliders and their descendants, so no set $S\subset V\setminus\{u,v\}$ blocks this one-edge path. Therefore $u$ and $v$ are not d-separated by any admissible $S$, and the first step gives \begin{align*} \mathcal O(\{u\},\{v\},S)=0. \end{align*} Since deletion requires a positive oracle answer, the true edge between $u$ and $v$ is retained. Next fix non-adjacent vertices $u$ and $v$ in $G$. Define $S:=\operatorname{An}_G(\{u,v\})\setminus\{u,v\}$, where ancestors include the vertex itself. This set is an admissible candidate because $S\subset V\setminus\{u,v\}$. We now verify directly that the [Moralized Ancestral Graph Criterion][citetheorem:9670] applies. Take $A=\{u\}$, $B=\{v\}$, and $Z=S$. The ancestral set in the criterion is \begin{align*} W:=\operatorname{An}_G(\{u,v\}\cup S)=\{u,v\}\cup S. \end{align*} In the moral graph of the induced sub-DAG on $W$, the vertices $u$ and $v$ have no original edge because they are non-adjacent in $G$. They also cannot acquire a moral edge through a common child $w\in W$: if $u\to w\leftarrow v$ and $w\in\operatorname{An}_G(\{u,v\})$, then a directed path from $w$ to $u$ or to $v$ would combine with $u\to w$ or $v\to w$ to form a directed cycle, contradicting acyclicity of $G$. After deleting $S$ from the moralized ancestral graph, only $u$ and $v$ remain and there is no edge between them. Thus $S$ separates $u$ and $v$ in the moralized ancestral graph, so the criterion gives that $S$ d-separates $u$ and $v$ in $G$. The skeleton-deletion phase in the theorem statement treats every subset of $V\setminus\{u,v\}$ as an admissible candidate and is exhaustive: if some admissible candidate gives a positive oracle answer, then the pair is deleted. This is where the population-oracle assumption matters: the oracle does not estimate or approximate the conditional independence; it answers exactly. Hence d-separation by $S$ gives \begin{align*} \mathcal O(\{u\},\{v\},S)=1. \end{align*} The deletion rule therefore removes $\{u,v\}$ and records such an $S$ as $\operatorname{Sep}(u,v)$. The two directions together prove that the skeleton phase deletes precisely the non-edges of $G$ and retains precisely the edges of $G$. Thus the remaining undirected graph is the skeleton of $G$. [/guided] [/step] [step:Orient exactly the unshielded colliders of $G$] Consider distinct vertices $a,b,c\in V$ such that $\{a,b\}$ and $\{b,c\}$ are edges in the recovered skeleton and $\{a,c\}$ is not. Such a triple is an unshielded triple in the recovered skeleton, and by skeleton correctness it is an unshielded triple in $G$. The population PC algorithm orients \begin{align*} a \to b \leftarrow c \end{align*} if and only if $b\notin \operatorname{Sep}(a,c)$. We prove the needed unshielded-triple separating-set characterization directly. Let $S\subset V\setminus\{a,c\}$ be any set that d-separates $a$ and $c$ in $G$. If $b$ is a non-collider on the path $a-b-c$ and $b\notin S$, then the length-two path $a-b-c$ is active given $S$, because its only interior vertex is a non-collider not conditioned on. This contradicts d-separation, so every d-separating set for $a$ and $c$ contains $b$. If $b$ is a collider on the path $a-b-c$ and $b\in S$, then the same length-two path is active given $S$, because its only interior vertex is a collider that is conditioned on. This again contradicts d-separation, so no d-separating set for $a$ and $c$ contains $b$. Since $\operatorname{Sep}(a,c)$ was recorded from a true population conditional independence, it is a d-separating set for $a$ and $c$ in $G$. Therefore the PC collider rule orients $a\to b\leftarrow c$ exactly when $b$ is a collider in $G$. Hence the v-structures recovered by PC are exactly the v-structures of $G$. [/step] [step:Identify the Markov equivalence class from the recovered skeleton and v-structures] Let $\mathcal M(G)$ denote the Markov equivalence class of $G$, meaning the set of directed acyclic graphs on $V$ with the same d-separation relations as $G$. By the [[Verma-Pearl Markov Equivalence Characterization](/theorems/9691)][citetheorem:9691], two directed acyclic graphs on the same finite vertex set are Markov equivalent if and only if they have the same skeleton and the same unshielded colliders. The previous two steps show that the population PC algorithm has recovered exactly the skeleton of $G$ and exactly the unshielded colliders of $G$. Therefore, by the [Verma-Pearl Markov Equivalence Characterization][citetheorem:9691], these recovered data determine precisely the Markov equivalence class $\mathcal M(G)$. In particular, a DAG on $V$ lies in $\mathcal M(G)$ exactly when it has this skeleton and exactly these unshielded colliders; orientations that would create an additional unshielded collider are not consistent with the recovered equivalence-class data. [/step] [step:Close under Meek rules to obtain the CPDAG] The final phase of the standard population PC algorithm repeatedly applies the Meek orientation rules until no further orientation is possible. We use the convention built into the theorem statement: Meek closure is the sound and complete closure operation which, from a partially directed graph with the correct skeleton and exactly the unshielded colliders of a finite DAG Markov equivalence class, orients precisely the compelled edges and leaves precisely the reversible edges unoriented. By the previous step, the graph entering the Meek-rule phase is a partially directed graph on the finite vertex set $V$, has the correct skeleton for $\mathcal M(G)$, and has directed exactly the unshielded colliders of $\mathcal M(G)$ before Meek closure. Therefore the stated hypotheses for this Meek-closure convention are satisfied. Soundness gives that every directed edge produced by the rules is compelled in every DAG in $\mathcal M(G)$. Completeness gives that every compelled edge in $\mathcal M(G)$ is eventually oriented by the rules. Hence the final mixed graph has precisely the compelled directed edges and the reversible undirected edges of $\mathcal M(G)$. By the definition of the completed partially directed acyclic graph stated in the theorem, this final mixed graph is the CPDAG of the Markov equivalence class of $G$. Therefore the population PC algorithm returns the CPDAG of the Markov equivalence class of $G$. [/step]