Let G be a graph and u and v two vertices.

(1) Let H be a random graph where every edge of G is chosen with probability ½. Let p be the probability that there is a path between u and v in H.

(2) Let T be a random **orientation** of the graph G. Namely, every edge {x,y} is directed from x to y with probability ½ and otherwise it is directed from from y to x. Let q be the probability that there is a **directed** path from u to v in T.

**What is the relation between p and q?**

**Answer: p=q**

This is an old theorem of Colin McDiarmid:

Colin McDiarmid, General Percolation and random graphs, *Adv. Appl. Prob*. **13**, 40–60 (1981). (The paper at Jstor)

see also:

Svante Linusson, A note on correlations in randomly oriented graphs, Preprint 2009, arXiv:0905.2881.

I heard about it from Svante who learned about Colin’s result from Jeff Kahn. (A bunch of us are hanging now at the Mittag-Leffler Institute.)

Thanks all for the interesting discussion! James Martin has also guessed one possible correct generalization.

Test your intuition (1), test your intuition (2), test your intuition (3), answer to (3)-

### Like this:

Like Loading...

*Related*

Thanks for the puzzle.

The McDiarmid paper also mentions the probability that the resulting graph has a Hamiltonian cycle. Let p be this probability under (1) and q be this probability under (2). The paper says

p <= q

I wonder if its also true that

2 p <= q,

since every undirected cycle can be oriented into two directed cycles.