یک گراف ساده‌ی ‎$G$‎ داریم. می‌خواهیم به هر یال مانند ‎$e$‎، یک عدد حقیقی مانند ‎$f(e)$‎ نسبت دهیم، طوری که شروط زیر برقرار باشد:

• برای هر یال مانند ‎$e$‎ داشته باشم: ‎$0 \leq f(e) \leq 1$.
• مجموع اعداد یال‌های متصل به هر رأس، حداکثر ‎۱‎ باشد.

بیشینه‌ی ممکن مجموع اعداد یال‌های ‎$G$‎ را، ‎$max(G)$‎ می‌نامیم. حال هر یک از قسمت‌های زیر را حل کنید.

1. ثابت کنید اگر گراف داده شده، دوبخشی باشد، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎۱‎ را نسبت داد، طوری که مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود.
2. ثابت کنید اگر گراف داده شده، دور زوج نداشته باشد، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎$\frac{1}{2}$‎ و ‎۱‎ را نسبت داد، طوری که مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود. ‎
3. ثابت کنید برای هر گراف داده شده، می‌توان به هر یال، یکی از اعداد ‎۰‎ و ‎$\frac{1}{2}$‎ و ‎۱‎ را نسبت داد، مجموع اعداد یال‌های ‎$G$‎، برابر ‎$max(G)$‎ شود. ‎‎‎ ‎

• سوال قبل