Euler gráftétele lapokról, csúcsokról és élekről

Tekintsük a legalapvetőbb gráfban, amikor csak egy csúcs van az egyenlet igaz. Ezzel a gráffal a következő két dolgot művelhetjük:

Ha nem adunk hozzá újabb csúcsot, akkor csak két meglévő csúcsot köthetünk össze. Ebben az esetben viszont mindig keletkezik egy új lap (mivela gráf síba rajzolható), a két összekötött csúcs között van út az újonnan behúzott él nélkül is, így ezzek együt körbezárnak az élek egy lapot. Hasonlóan ekkor is az egyenlet igaz marad, hiszen az élek és lapok számai is -gyel nő.

A fönt leírtak miatt több lehetőség nincs.

A legalapvetőbb gráfból mindegyik összefüggő gráfba el lefeht jutni a következők miatt. Először rajzoljuk föl a csúcsokat. Mivel mindegyik össze van kötve valamelyik másikkal(mert összefüggő), így egy csúcs és egy él behúzúsának véges sok megismétlésével lerajzoluk a csúcsokat. A még össze nem kötött csúcsokat a következőkben összekötjük. Így a fönt leírt két lépéssel le lehet rajzolni az összes összefüggő gráfot.

Mivel az egyenlet a triviális gráfnál igaz, és minden lépeésben igaz is marad, így igazoltuk a tételt.

Bizonyítás

Bizonyítsuk be a tételt teljes indukcióhoz hasonlóan!

Ha hozzáadunk egy újabb csúcsot, akkor ahhoz, hogy összefüggő maradjon, össze kell kötni azt valamelyik csúccsal (; lap nem képződhet, mert az új csúcs csak egy másikkal van összekötve.) Ebben az esetben a csúcsok és élek száma -gyel nő, így az egyenlet mindkét oldalához -et adunk hozzá, így ez igaz marad.