MIT
82
Proof (edge count)
lEdge e included with probability r / ce
lSo expected number is S r / ce
lWe saw  S 1/ce  £  n
lSo expected number at most  r n