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

• سوال بعد
• سوال قبل