A probabilistic problem in graphs Let $G$ be a (simple) graph. Each edge will be deleted or will be reminded with probability $\frac 12$ (independent from the other edges). Let $P_{AB}$ be the probability that (after this process) the vertices $A$ and $B$ are connected. On the other hand starting from $G$ we give each edge a direction with probability $\frac 12$ (and independent). Let $P_{A\longrightarrow B}$ be the probability that there is a directed path from $A$ to $B$. Show that $P_{AB} = P_{A\longrightarrow B}$.    

It is possible to prove this by induction using contraction of a neighbour set of $A$:
It is enough to count all admissible configurations, because any configuration has the same probability $(\frac 12)^{|E(G)|}$.
The number of admissible configurations in the non-oriented case where $A$ is adjacent to exactly the subset $S$ of its neighbour is given by the admissible configurations of the graph $G$ with the point $A$ removed and the set $S$ contracted to a single vertex which is the new vertex $A$.
The number of admissible configurations in the oriented case where $A$ has out-going arcs exactly to the set $S$ are again the admissible configurations of the graph $G$ with the point $A$ removed and the set $S$ contracted to a single new vertex $A$.
If $S$ is empty, both numbers are 0. If $A=B$, then both numbers are simply all configurations regardless of $S$. If $A$ and $B$ are different points and $S$ is not empty, the removal of $A$ and the contraction give a smaller version of the same problem (for example with respect to the distance between $A$ and $B in the original graph) that has the same number of configurations by induction.
The edges that have been removed during contraction have two possible states in both cases, so their contribution to the total number of configuration is the same.
