Proof (approximation)
l Basic idea: in a k-strong component,
edges get sampled with prob. r / k
» original sampling theorem works
l Problem: some edges may be in
stronger components, sampled less
l Induct up from strongest components:
» apply original sampling theorem inside
» then “freeze” so don’t affect weaker parts