قضیه دیلورث

جهت اثبات قضیهٔ دیلورث با استفاده از قضیهٔ کونیگ برای یک مجموعهٔ جزئاً مرتب S با n عضو، یک گراف دوبخشی G = (U, V, E) تعریف می کنیم به طوری که U = V = S و (u, v) یک یال در G است به طوری که u < v در S باشد. با توجه به قضیهٔ کونیگ، یک جورسازی M و یک مجموعه از رئوس C در G وجود دارد، به طوری که هر یال در گراف شامل حداقل یک رأس از C باشد و تعداد اعضای M و C، برابر m باشد. گیریم A مجموعه‌ای از اعضای S باشد که به هیچ رأسی از مجموعهٔ C مرتبط نباشند، بنابراین A حداقل m-n عضو دارد. گیریم P خانواده‌ای از زنجیرهایی باشد که اگر یال (x,y) در جورسازی M باشد، آنگاه زنجیرهایی که شامل x و y می‌باشد را در یک زنجیر قرار می‌دهد، بنابراین P هم شامل n-m زنجیر می باشد. پس ما یک افراز ترتیب جزئی به زنجیرها و یک پادزنجیر ساخته‌ایم که اندازه هر دو یکسان است.

برای اثبات قضیهٔ کونیگ با استفاده از قضیهٔ دیلورث برای یک گراف دوبخشی G = (U,V،E)، یک ترتیب جزئی روی رأس های G تشکیل می دهیم که در آن u < v، دقیقاً وقتی که u در V، v در Uو یک یال در E، از u به v، وجود داشته باشد. طبق قضیهٔ دیلورث، یک پادزنجیر A و یک افراز ترتیب جزئی به خانواده P از زنجیرها وجود دارند، که هر دو اندازهٔ مشابه دارند. اما فقط زنجیرهای مهم در ترتیب جزئی، جفت اعضای مرتبط به یال‌ها در گراف می باشد. بنابراین زنجیرهای مهم در P، تشکیل یک جورسازی در گراف می دهند و مکمل A، یک پوشش رأسی در G با تعداد اعضای برابر با جورسازی، تشکیل می دهد. این اتصالات در جورسازی گراف دوبخشی، اجازه می‌دهد که طول هر ترتیب جزئی، بتواند در زمان چند جمله‌ای محاسبه شود.