הוכחות מתמטיות/מתמטיקה בדידה/בגרף דו צדדי d-רגולרי יש זיווג מושלם

$G=(V_1,V_2,E)$ גרף דו-צדדי d-רגולרי אזי ב- $G$ זיווג מושלם.

הוכחה: בכל תת קבוצה $S\subset V_1$ חלות $|S|d$ צלעות. וכן ב- $\mathrm{\Gamma }(S)$ חלות $|\mathrm{\Gamma }(S)|d$ צלעות.

מאחר והגרף d-רגולרי, כל צלע שחלה ב- $S$ חלה גם ב- $\mathrm{\Gamma }(S)$

ולכן כמובן ש- $|d\mathrm{\Gamma }(S)|\ge |dS|$ ומאחר ש- d מספר טבעי: $|\mathrm{\Gamma }(S)|\ge |S|$