G = ( V 1 , V 2 , E ) {\displaystyle G=(V_{1},V_{2},E)} גרף דו-צדדי d-רגולרי אזי ב- G {\displaystyle G} זיווג מושלם.
הוכחה: בכל תת קבוצה S ⊂ V 1 {\displaystyle S\subset V_{1}} חלות | S | d {\displaystyle |S|d} צלעות. וכן ב- Γ ( S ) {\displaystyle \Gamma (S)} חלות | Γ ( S ) | d {\displaystyle |\Gamma (S)|d} צלעות.
מאחר והגרף d-רגולרי, כל צלע שחלה ב- S {\displaystyle S} חלה גם ב- Γ ( S ) {\displaystyle \Gamma (S)}
ולכן כמובן ש- | d Γ ( S ) | ≥ | d S | {\displaystyle |d\Gamma (S)|\geq |dS|} ומאחר ש- d מספר טבעי: | Γ ( S ) | ≥ | S | {\displaystyle |\Gamma (S)|\geq |S|}
