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

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

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

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