Egyszerű gráf: olyan gráf, melyben nincsenek többszörös-, és hurokélek. (két csúcs max csak egyszer van összekötve éllel, és egyik csúcsból sem vezet önmagába él)

Indirekt módon bizonyítjuk ezt. Tegyük fel, hogy létezik ilyen gráf. Ha van egy `n` csúcsú gráfunk, akkor egy csúcsnak 0-tól `n-1`-ig terjedő fokszáma lehet. Mivel `n` db csúcs van, így ha mindegyik különböző, akkor 0-tól `n-1`-ig mindegyik fokszámnak elő kellene fordulnia. De ez lehetetlen, hiszen az `n-1` fokszámúból mindegyik másikba is kellene vezetnie élnek, így a 0-asba is, de a 0 fokszámú csúcsba nem vezet él. Ez ellentmondás, tehát nem létezik ilyen egyszerű gráf. Ennek egy következménye, hogy tetszőleges egyszerő gráfban mindig található legalább 2 azonos fokszámú csúcs.