Hogyan mutassam meg, hogy tetszőleges gráfban a páratlan fokú pontok száma páros?

Legyen a bizonyítás indirekt. Ha a gráfban egy v csúcs fokszámát d(v) jelöli, V a csúcshalmaz, és e az élek száma, akkor tudjuk, hogy szumma(d(v))=2e . Ha a gráfban páratlan sok olyan csúcs van, melyre d(v) páratlan, akkor a jobboldalon páratlan szám áll, hiszen páratlan sok páratlan szám összege szintén páratlan, ehhez további páros számokat adva az összeg paritása nem változik. A baloldalon viszont páros szám szerepel, így ellentmondáshoz jutottunk.