گرافی جهت دار میسازیم اینجوری که $|A| + |B|$ راس داشته باشه و هر راس متناظر با یه عضو تو $A \cup B $ باشه. (دقت کنید که $A$ و $B$ مجزا هستن!). عدد متناظر راس $v$ رو $f(v)$ تعریف میکنیم. تو گرافمون از راس $v$ به راس $u$ یال میکشیم اگر و نتها اگر یکی از این دو شرط برقرار باشه:
1.یال های آبی : $f(u)\in A$ و $f(u) = f(v) + a$
2. یال های قرمز : $f(u) \in B$ و $f(u) = f(v) - b$
بیاین مجموع درجات خروجی ( = مجموع درجات ورودی) این گراف رو $\sum d$ بنامیم و حساب کنیمش! بنابه فرض مسئله از هر راس حداقل 1 یال خارج میشود... پس : $\sum d \ge |A| + |B|$
از طرفی امکان نداره که یک راس بیش از یک یال ورودی داشته باشه! چون یال های ورودی هر راس بوضوح همرنگن و بخاطر همین امکان نداره $x$ و $y$ متفاوت پیدا بشه که $x + a = c$ و $y + a = c$ .(فرض کردیم یال های ورودی آبین) پس در نهایت : $\sum d \le |A| + |B|$
پس معلوم شد که $\sum d = |A| + |B|$ پس هر راس دقیقن یک یال ورودی و یک یال خروجی داره. همچین گرافی اجتماع یسری دور مجزاست!
خب راس دلخواه $x$ رو در نظر بگیریم. دوری که $x$ توشه $t$ تا یال آبی و $t'$ تا یال قرمز داره. آنگاه میتونیم بگیم:
$ f(x) = f(x) + a \times t - b \times t' \Rightarrow a \times t = b \times t'$
اگه برای هر دور تو گرافمون این معادله ی بالا رو بنویسم و همرو با هم جمع کنیم میرسیم به
$a \sum t = b \sum t' $
$\sum t$ = تعداد یال های آبی = $|A|$ و $\sum t'$ = تعداد یال های قرمز = $|B|$
پس : $a|A| = b|B|$ $^_^$