یک گراف $n$ راسی تقریباً همبند است اگر به ازای هر افراز رئوس $G$ به دو دسته‌ی $S$ و $T$ که $|T| \geq |S| \geq n/10$، حداقل یک یال بین این دو دسته وجود داشته باشد. کم‌ترین مقدار $k$ را در نظر بگیرید که که اگر یک گراف $n$-راسی با رئوس $1, 2, \dots, n$ و $k$ یال درنظربگیرید (تعداد این یال‌ها $C(n,k)$ می‌باشد)، به احتمال حداقل $1/2$ این گراف تقریباً همبند باشد. پیچیدگی تابعی ($\Theta$) $k$ را به‌دست آورید.