Population PC correctness under faithfulness

With an exact conditional independence oracle and faithfulness of a directed acyclic graph, the skeleton phase of the PC algorithm deletes precisely the nonedges. A true edge cannot be D-separated by a set excluding its endpoints. For nonadjacent vertices, choose the later vertex $v$ in a topological ordering; its parents separate it from the earlier nonparent. True parent edges survive throughout, so this separator remains available among the algorithm's candidate neighbour sets. For an unshielded triple $u-v-w$, any recorded separator of $u,w$ excludes $v$ exactly when the triple is an unshielded collider. The skeleton and collider characterization of Markov equivalence therefore identifies the correct equivalence class. Directions compelled throughout that class give its completed partially directed acyclic graph.