Az azonos fokszámú csúcsok tétele

Tegyük föl, hogy minden csúcs fokszáma különböző! Ekkor az csúcsú gráfban a fokszámok biztosan . A fokszámú semelyik csúccsal sincs összekötve, míg az fokszámú csúcsnak minden másik csúccsal össze van kötve. Ez ellentmondás, tehát hamis feltételből indultunk ki, így a tételt igazoltuk.

A tétel végtelen (végtelen csúcsból álló gráf) egyszerű gráfra nyilvánvalóan nem igaz, erre könnyen adható ellenpélda:

Bizonyítás