قضیه هال

قضیه هال یا قضیه هال (۱۹۳۵) قضیه ای مربوط به شاخه ترکیبیات و قضیهٔ گراف در ریاضی است. این قضیه که به ریاضی دان انگلیسی، فیلیپ هال نسبت داده می شود، شرط لازم و کافی برای وجود تطابق کامل در گراف های دوبخشی را بیان می کند. گراف های دوبخشی به گراف هایی گفته می شوند که رأس ها به دو دسته مجزا قابل افراز هستند بگونه ای که تمامی یال های گراف بین گره های بین دو دسته مختلف باشند.
کتاب آشنایی با نظریه گراف اثر دوگلاس بی.وست
http://en.wikipedia.org/wiki/Marriage_theorem
۱-مسیر M-متناوب: مسیری است که یالهای آن یکی در میان در تطابق M باشد.
۲-مسیر M-افزوده: مسیر M-متناوبی است که یالهای ابتدایی و انتهایی آن داخل تطابق M نباشد.
در تطابق بیشینه مسیر M-افزوده وجود ندارد زیرا اگر فرض کنیم که یک مسیر M-افزوده در تطابق بیشینه ما وجود داشته باشد می توان با حذف یالهایی از مسیر افزوده که در تطابق هستند از تطابق و اضافه کردن یالهایی که در تطابق نیستند به تطابق اندازه تطابق را یک یال افزایش داد که این متناقض با بیشینه بودن تطابق است.