الگوریتم صورت سوال رو انقدر پیش میبریم تا رئوس گراف تمام بشه. (یعنی شرط $k$-آلوده نبودن را برمیداریم.) $U_i$ رو تعریف میکنیم $i$ ـمین راسی که طی الگوریتم انتخاب میشه. $A_i$ رو هم تعریف میکنیم تعداد یال هایی که رئوس $U_1, U_2, ..., U_i$ آلوده میکنن.
همچنین یکی از مجموعه های $k$-آلوده ی ماکسیمم رو $O$ مینامیم و $O_i$ رو تعریف میکنیم $i$ـمین راس داخل $O$ وقتی که رئوس $O$ رو بر حسب درجات بصورت نانزولی مرتب کرده باشیم.
اگه $S$ مجموعه ای از رئوس گراف باشه, $f(S)$ رو تعریف میکنیم مجموعه یال هایی که هر دو راس انتهاییش داخل $S$ هستن.

فرض کنیم الان در مرحله ی $i$ ـم هستیم و راس $v$ رو الگوریتم گفته شده به مجموعه $U$ اضافه میکنه. چون درجه ی الان راس $v$ یعنی تعداد یال هایی که یک سرشون راس $v$ هست و سر دیگرشون توی $U$ نیست, به اندازه ی درجه ی الان راس $v$ در گراف به تعداد یال های آلوده اضافه میشه.
از طرف دیگه, چون هر بار راسی که درجه ی الانش مینیمم هست رو انتخاب میکنیم, درجه الان $v$ حداکثر برابر $d_{O_i}$ ـه. (چون تا الان حداکثر $i-1$ تا راس از گراف حذف شدن. پس درجه ی الان راس $v$ که کوچیکتر-مساوی درجه ی اصلی راس $v$ هست, حداکثر از درجه ی $i-1$ راس دیگه بزرگتره که در بدترین حالت که همشون عضو $O$ باشن, درجه ی الان $v$ برابر درجه ی $O_i$ میشه.)

حالا یکسری $fact$ و بعدش نتیجه گیری! :

۰)تعداد یال هایی که $O$ آلوده میکنه برابره با $\sum_{u \in O}^{}{d_u} - f(O)$

۱)از طرفی واضحه که $\sum_{u \in O}^{}{d_u} \ge 2f(O)$

۲)از نکات واضح دیگه اینه که $\sum_{u \in O}^{}{d_u} \ge 2\sum_{1\le i \le \frac{|O|}2 }d_{O_i}$
پس در نتیجه داریم : $A_{\frac{|O|}{2}} \le\sum_{1\le i \le \frac{|O|}2 }d_{O_i} \le\frac{\sum_{u \in O}^{}{d_u} } 2 \le \sum_{u \in O}^{}{d_u} -f(O) \le k$
پس $\frac{|O|}{2}$ تا عضو اول $U$ حداکثر $k$ یال آلوده میکنند پس خروجی این الگوریتم حداقل اون تعداد راس داره! $^_^$