Theorem as stated is not true. The problem with the current proof 
is that an alternative 'incorrect' structure may share the skeleton 
of the true structure $G^*$. In this case, it is not true that ..

Two weaker results do hold: 
1. All results in the paper are correct, assuming that we replace the requirement 
of recovering the correct structre by recovering a graph which shares a skeleton 
of the correct strucutre. 

2. All results in the paper are correct, provided that we change the definition 
of $IC_B$. Instead of the 'minimal information carried by an edge', it should be
'the minimal information lost by an edge flipped'. To see this, 

Thanks to  Peter Spirtes, and David Sontag and Eliot Brenner for pointing the errors in the current version.