The PC algorithm recovers the oracle CPDAG

By [F2], every d-separation in $G$ is a conditional independence in its law. By [F3], every conditional independence is a d-separation. Since the oracle is exact by [F1], it answers “independent” exactly for d-separated pairs and sets.

The skeleton search terminates. If $\mathrm{\mid }V\mathrm{\mid }\le 1$, it has no pairs to test and stops at level $0$. Otherwise, at each level it processes finitely many pairs and finitely many subsets. An endpoint has at most $\mathrm{\mid }V\mathrm{\mid }-2$ neighbors other than the other endpoint, so at level $\mathrm{\ell }=\mathrm{\mid }V\mathrm{\mid }-2$ no remaining edge can meet the condition requiring at least $\mathrm{\ell }+1$ such neighbors; the level therefore cannot be incremented past this finite bound. The orientation phase scans finitely many rule instances on the finite vertex set. Every successful application directs one previously undirected edge, which is never undirected again, so there are at most $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }V\mathrm{\mid }}{2}\right)$ successful applications before a scan finds none. Both phases, and hence the algorithm, terminate.

For a nonadjacent pair, acyclicity permits labeling its endpoints $i,j$ so that $j$ is not a descendant of $i$. Put $S={\mathrm{pa}}_G(i)$, which excludes both endpoints. Every path starting with an arrow into $i$ is blocked by its first internal vertex, a parent in $S$ and a noncollider. On any path starting with an arrow out of $i$, there must be a first reversal of arrow direction, since $j$ is not a descendant of $i$. The vertex at that reversal is a collider reached by a directed path from $i$. It cannot have a descendant in $S$, since a directed path from that collider to a parent of $i$ would close a directed cycle through $i$. This path is also blocked by [F8]. Thus $S$ d-separates the endpoints.

Every true skeleton edge remains in the search graph: by [F4] no allowed conditioning set d-separates its endpoints, so step 1.1 makes every oracle answer dependent. For a nonedge, step 1.3 supplies $S={\mathrm{pa}}_G(i)$ after possibly interchanging endpoints. Every vertex of $S$ remains adjacent to $i$, since all true edges remain. At each level $\mathrm{\ell }<\mathrm{\mid }S\mathrm{\mid }$ while this nonedge remains, endpoint $i$ has at least $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\ell }+1$ other neighbors. The stopping condition therefore cannot stop before level $\mathrm{\mid }S\mathrm{\mid }$. If the nonedge has not already been deleted, at that level the search either deletes it on an earlier separating set or tests $S$ and deletes it. Thus the returned skeleton is exactly the skeleton of $G$.

Every set recorded when an edge is deleted was accepted by the exact oracle. By step 1.1 it d-separates the deleted endpoints. Since the skeleton from step 2.1 is exact, each unshielded triple is an unshielded triple of $G$; [F5] shows the algorithm orients its middle vertex as a collider exactly when it is a collider in $G$.

The algorithm then applies R1–R3 to closure. Its pattern has the exact skeleton and exactly the unshielded colliders of $G$ by steps 2.1–3.1. Applying [F7] gives the CPDAG of $G$. By step 1.2 the finite procedure terminates, so this is the algorithm's output.