یک گراف ساده‌ی $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)$ شود.