A gráf csúcsainak számára vonatkozó teljes indukcióval bizonyítunk. Ha $G$ minden csúcsából páros sok él indul ki, akkor az állítás nyilvánvaló, ui. a csúcsokat véve az egyik résznek, az üres halmazt véve a másik résznek a kívánt felosztást kapjuk, hiszen $G\text{'}=G$ megfelelő. Ide tartozik az 1 csúcsú egyszerű gráf esete is, aminek nincsen éle.
Tegyük fel, hogy $n$ csúcsú gráfokra már beláttuk az állítást; bizonyítsuk be az $n+1$ csúcsú $G$ gráfra is. Feltehetjük, hogy $G$-nek van legalább egy páratlan fokú $P$ pontja. Legyenek a $P$ szomszédai $A_1$, $A_2$, $\text{...}$, $A_{2k+1}$. A $G$-ből hagyjuk el a $P$-t és a belőle induló éleket, továbbá, ha $A_i$-t és $A_j$-t él köti össze, akkor ezt az élt is hagyjuk el; ha pedig nem köti őket össze él, akkor kössük őket össze éllel. Jelöljük az így kapott gráfot $G_1$-gyel.
$G_1$  $n$ csúcsú egyszerű gráf, ezért az indukciós feltétel szerint pontjai két diszjunkt $H_1$ és $H_2$ részre oszthatók úgy, hogy az ezek közt futó élek elhagyásával keletkező $G_1\text{'}$ gráf minden pontjának foka páros. A $H_1$ és $H_2$ részek közül az egyikben páros, a másikban páratlan számú szerepel az $A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_{2k+1}$ pontokból. Az általánosság csorbítása nélkül feltehetjük, hogy $H_1$-ben az $A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_{2l}$, $H_2$-ben az $A_{2l+1}\mathrm{,}{A}_{2l+2}\mathrm{,}\text{...}\mathrm{,}{A}_{2k+1}$ csúcsok szerepelnek. A $G$ pontjait osszuk a $H_1\cup \left\{P\right\}$ és $H_2$ diszjunkt részekre, és legyen $G\text{'}$ a két rész közti élek elhagyásával keletkező gráf. Állítjuk, hogy $G\text{'}$ minden pontjának foka páros, ami igazolja a feladat állítását.
$G\text{'}$-ben a $P$ szomszédai az $A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_{2l}$ pontok, $P$ foka tehát páros. A $P$-től és az $A_i$-ktől különböző csúcsoknak a $G\text{'}$-ben ugyanazok a szomszédai, mint $G_1\text{'}$-ben, tehát az ilyen csúcsok foka is páros $G\text{'}$-ben. Már csak az $A_i$ csúcsok fokszámáról kell belátnunk, hogy párosak.
Tekintsünk egy $A_i$ csúcsot, legyen ennek foka a $G_1\text{'}$-ben $k_1$, a $G\text{'}$-ben pedig $k$. Mivel $k_1$ páros, azért elegendő igazolnunk, hogy $k+k_1$ páros. Ha $A_i$ $H_1$-beli, akkor $G\text{'}$- és $G_1\text{'}$-beli szomszédainak együttes számbavételénél a $H_1\setminus \left\{A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_{2l}\right\}$-be eső szomszédokat pontosan kétszer, az $\left\{A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_{i-1}\mathrm{,}{A}_{i+1}\mathrm{,}\text{...}\mathrm{,}{A}_{2l};P\right\}$-be esőket pontosan egyszer számoltuk. Ezért $k+k_1$ (két páros szám összegeként) páros. Hasonlóan, ha $A_i$ $H_2$-beli, akkor $G\text{'}$- és $G_1\text{'}$-beli szomszédainak együttes számbavételénél a $H_1\setminus \left\{A_{2l+1}\mathrm{,}{A}_{2l+2}\mathrm{,}\text{...}\mathrm{,}{A}_{2k+1}\right\}$-be eső szomszédokat pontosan kétszer, az $\left\{A_{2l+1}\mathrm{,}{A}_{2l+2}\mathrm{,}\text{...}\mathrm{,}{A}_{i-1}\mathrm{,}{A}_{i+1}\mathrm{,}\text{...}\mathrm{,}{A}_{2k+1}\right\}$-be esőket pontosan egyszer számoltuk. Tehát $k+k_1$ (megint csak két páros szám összegeként) páros.
Ezzel a feladat állítását bebizonyítottuk.