Proof (edge count)
l
Edge
e
included with probability
r
/
c
e
l
So expected number is
S
r
/
c
e
l
We saw
S
1
/
c
e
£
n
l
So expected number at most
r
n
