فرض کنید گراف $G$ یک گراف $n$ راسی کامل جهت‌دار باشد که جهت یال بین دو راس $u$ و $v$ به سمت راسی باشد که کمیته مسابقات در صورت انتخاب بین دو کشور $u$ و $v$ آن کشور را انتخاب می‌کند (و کشور دیگر را حذف می‌کند).

اگر کشور $r$ برای میزبانی مسابقات انتخاب شده باشد، می‌دانیم به ازای هر راس $u \neq r$ یک کشور $f(u)$ وجود دارد که باعث حذف کشور $u$ شده است. همچنین واضح است که‌یال بین دو راس $u$ و $f(u)$ به سمت $f(u)$ است. فرض کنید از گراف $G$ یال‌های بین $u$ و $f(u)$ ها را انتخاب کنیم و بقیه‌یال‌ها را حذف کنیم و گراف جدید را $G'$ بنامیم. می‌توان نشان داد که گراف $G'$ یک درخت ریشه دار به ریشه $r$ است که تمام یال‌های آن به سمت ریشه است. پس از تمام رئوس گراف یک مسیر به سمت راس $r$ وجود دارد.

همچنین در صورتی که تمام رئوس گراف مسیری به سمت راس $r'$ داشته باشند، اجتماع این مسیرها گرافی شبیه به $G'$ به ریشه $r'$ تولید می‌کند که می‌توانیم با استفاده از آن طوری مراحل انتخاب کشور میزبان را بسازیم که کشور $r'$میزبان مسابقات شود.

پس کشور $u$ قابلیت میزبانی مسابقات را دارد اگر و فقط اگر در گراف $G$ تمام رئوس مسیری به سمت راس $u$ داشته باشند.

حال برای به‌دست آوردن تمام رئوسی که شرط بالا را دارند، کافیست گراف را به مولفه‌های قویاً همبند افراض کنیم و رئوس مولفه‌ای که به هیچ مولفه دیگر یالی ندارد را به عنوان جواب انتخاب کنیم.

پیچیدگی

افراض گراف به مولفه‌های قویاً همبند را می‌توان در زمان $o(n+e)$ انجام داد. همچنین انتخاب مولفه‌ای که به مولفه‌های دیگر یالی ندارد را می‌توان در زمان $o(e)$ انجام داد. پس سوال را می‌توان در زمان $o(n+e) = o(n^2)$ حل کرد.