قضیه برژ

در نظریه گراف، قضیه برگه بیان می‌کند که یک مچینگ M از گراف G ماکسیمم است، اگر و تنها اگر مسیر M-افزوده(مسیری که یال هایش یکی در میان در مچینگ باشد و همچنین اولین و آخرین یال هم جزء مچینگ نباشد) نداشته باشیم. قضیه ایست که Claude Berge ریاضیدان فرانسوی درسال 1957 آن را به اثبات خود در آورد.

اثبات

ابتدا به اثبات طرف اول رابطه بالا می پردازیم: از برهان خلف استفاده کرده و فرض می کنیم که وقتی مسیر M-افزوده داشته باشیم در نتیجه گراف ماکسیمم نیست. به سادگی می توان گفت، در مچینگ M از G با مسیر M-افزوده P، مچینگ M` با تعداد یال‌های بیشتر وجود خواهد داشت به طوری که $M'=M\Delta\,P$ (یال هایی که دقیقا یک بار در یکی از M و P آمده اند)

اثبات عکس رابطه نیز بدین صورت است: فرض کنید M' یک مچینگ بزرگتر از مچینگ M) M-افزوده ندارد) است. در نتیجه $M'\Delta\,M$ را در نظر بگیرید. این گراف شامل راس هایی با حداکثر درجه 2 است. (چون هر راس در هر کدام از مچینگ‌ها حداکثر می تواند درجه 1 داشته باشد) درنتیجه گراف حاصل شامل یک سری دور با تعداد رئوس زوج و مسیر خواهد بود که یال‌ها یکی در میان از M و M' هستند و همچنین تعداد یال‌های M' از تعداد یال‌های M بیشتر است. حال چون در دورهای زوج تعداد یال هایی که از M هستند با تعداد یال‌های از M' برابر استT در نتیجه مسیری وجود دارد که تعداد یال‌های آن از M' بیشتر از دیگری باشد که یک مسیر M-افزوده را نشان می دهد. تناقض

منابع

کتاب مقدمه ای بر نظریه گراف (نگارش دوم2)، نوشته دووگلاس بی وست.

http://en.wikipedia.org/wiki/Berge%27s_lemma