در این قسمت 2 سوال و 1 پیوند به سوال بیرونی وجود دارد
ثابت کنید در هر گرافی تطابق ماکسیمال حداقل نصف تطابق ماکسیمم است.
یک گراف ساده داریم می خواهیم به هر یال مانند $e$ یک عدد $f(e)$ نسبت دهیم که بین صفر و یک باشد و این شرط برقرار باشد که مجموع یال های متصل به هر راس حداکثر یک باشد. بیشینه ی مجموع عدد یال ها را max گراف مینامیم. ثابت کنید میتوان طوری عدد ها را تعیین کرد که اولا یا 0 باشند یا $\frac 1 2$ یا 1 ثانیا مجموعشان max گراف شود.