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

$G=(V_{1},V_{2},E)$ גרף דו-צדדי d-רגולרי אזי ב- $G$ זיווג מושלם.

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

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

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