הוכחות מתמטיות/מתמטיקה בדידה/משפט החתונה של הול

בגרף דו-צדדי $\displaystyle G=(V_{1},V_{2},E)$ בו $\displaystyle |V_{1}|=|V_{2}|$ יש זיווג מושלם אם ורק אם לכל קבוצה $S\subseteq V_{1}$ מתקיים $\displaystyle |\Gamma (S)|\geq |S|$

הוכחה

כיוון אחד: הוכחת הכרחיות. נוכיח שאם קיים זיווג מושלם בהכרח מתקיים התנאי $\displaystyle |\Gamma (S)|\geq |S|$ זיווג מושלם של קבוצה אחת לשנייה מקביל להתאמה חד חד ערכית ועל. לא ניתן לעשות התאמה חד חד ערכית אם קיימת תת קבוצה שמספר האיברים בתמונתה קטן ממספר איבריה. לכן אם קיים זיווג מושלם ודאי שיתקיים $\displaystyle |\Gamma (S)|\geq |S|$ כאשר $\Gamma (S)$ היא קבוצת השכנים של של S

כיוון שני: הוכחת מספיקות. נניח שהתנאי מתקיים ונוכיח כי קיים זיווג מושלם. ההוכחה באינדוקציה.

בסיס האינדוקציה: אם $\displaystyle |V_{1}|=|V_{2}|=n=1$ קיימים שני קודקודים ובינהם צלע - הטענה מתקיימת.

נניח נכונות עבור $\displaystyle |V_{1}|=n-1$ ונוכיח עבור $\displaystyle |V_{1}'|=n$.

תהא קבוצה חלקית ממש: $\displaystyle S\subseteq V_{1}'$. אם התנאי החזק יותר מתקיים, אזי מתקיים לכל תת קבוצה: $\displaystyle |\Gamma (S)|\geq |S|+1$

ולכן קיים קודקוד $x\in V_{1}'$ שיש לו שני שכנים: $\displaystyle \Gamma (x)={y_{1},y_{2}}$.

נבחר באופן שרירותי אחד מהקודקודים $\displaystyle {y_{1},y_{2}}$ ונסיר את הקודקודים $\displaystyle {x,y_{1}}$ ואת הצלעות החלות בהם, כך שנוצר גרף חדש: ${\hat {G}}=G\setminus {\{x,y_{1}\}}$.

כמובן שלכל תת קבוצה $S\subset V_{1}\setminus {x}$ מתקיים $\displaystyle |\Gamma (S)|\geq |S|$ ולפי הנחת האינדוקציה, זהו גרף עם זיווג מושלם. נוסיף לו את הזוג $x,y_{1}$ וזהו זיווג מושלם ב $\displaystyle G$.

אם התנאי החזק לא מתקיים הרי שקיימת תת קבוצה חלקית ממש כך ש $\displaystyle |\Gamma (S)|=|S|$

(אם הקבוצה לא חלקית, לכל קודקוד ב $V_{1}$ מתאים קודקוד יחיד ב$V_{2}$, ואז המשפט מתקיים).

נתבונן בתת הגרף $S\cup \Gamma (S)$: הוא עומד בתנאי משפט הול, ולפי הנחת האינדוקציה מכיל זיווג מושלם.

נותר לזווג את $V_{1}\setminus S$ ל- $V_{2}\setminus \Gamma (S)$; ומאחר שמתקיים $\displaystyle |\Gamma (S)|=|S|$ הרי שקבוצת הקודקודים הנותרת מקיימת את התנאי החזק יותר.