Gráfelmélet. Jelöljük egy fa elsőfokú pontjainak a számát f1-gyel, a kettőnél nagyobb fokúnak a számát pedig c-vel. Hogyan bizonyítsam be, hogy ha legalább két pontja van a gráfnak, akkor f1>=c+2?

Legelőször is töröljünk minden kettő fokú csúcsot a gráfból: ha A foka kettő azaz két szomszédja van, mondjuk B és C akkor tekintsünk egy új gráfot ahol az AB és AC éleket AC helyettesíti. Ez a többi pont fokszámán nem változtat. (B szomszédai között A-t C-vel helyettesítettük, és viszont, más pont meg nem érintett mert A fokszáma kettő volt)

Ezt ismételten hajtsuk végre amíg nincs kettő fokszámú pont a gráfban.

Most szemeljünk ki két nem szomszédos levelet (ha van. ha nincs akkor c=0 és f1=2) és a köztük lévő utat. Most nézzünk egy nem-levél pontot az úton: P nem levél, akkor van Q1, Q2, Qn szomszédja ahol n=d(P)-2 ahol Qi nincs az eredeti úton. PQ1 egy út első éle ami levélhez vezet -- és ez csak olyan levél lehet amit még nem érintettünk hiszen ez egy fa. Ez minden nem-levél pontra igaz amit a bejáráskor érintünk. Tehát az algoritmus a következő: indulásképpen van egy utunk amin van két levél és valahány nem levél pont. A bejárás során amikor egy nem levél ponthoz érkezünk akkor szemeljünk ki egy új levelet ami elérhető abból a pontból ilyen lesz hiszen ez egy véges fa és a pont foka kettőnél nagyobb. Sőt pont annyi ilyen levél lesz mint a pont fokszáma mínusz kettő -- azért mínusz kettő mert van az a pont ahonnan érkezünk és az a pont ahova eredetileg távozni akartunk.

A bejárás minden belső pontot érinteni fog. Volt tehát az eredeti két levél plusz minden belső ponthoz a fokszáma mínusz kettő számú új levél és minden pontot bejártuk.

Tehát, az egyenlőtlenségnél többet is tudunk, f1 éppenséggel 2 + sum(d(X)-2) minden kettőnél nagyobb fokú pontra.

Építsük fel a fát egyesével, mindig egy új csúcs hozzáadásával. Ezt úgy tehetjük, hogy a csúccsal együtt egy élet is hozzáadunk a fához: az él egyik vége egy már létező csúcs, a másik vége az új csúcs.

(Ugyanezzel a módszerrel igazolható az is, hogy minden fának eggyel több csúcsa van, mint éle.)

A kiinduló fa legyen a két csúcsból és egy élből álló fa. Erre teljesül a tétel, hisz f₁ = 2, c=0.

Indukciós feltétel: n csúcsú fára f₁ ≥ c+2

n+1-edik csúcs és a hozzá tartozó él hozzáadása:

Három eset lehet:

1) Az új élet levélhez (1 fokú csúcshoz) illesztjük:

Ekkor a levél 2 fokú csúccsá alakul, a hozzáadott csúcs pedig 1 fokú lesz. Vagyis f₁ és c is változatlan.

2) Az új élet 2 fokú csúcshoz illesztjük:

Ekkor a 2 fokú csúcs 3 fokúvá válik, a hozzáadott csúcs pedig 1 fokú lesz. Vagyis f₁ is és c is nő eggyel.

3) Az új élet 2-nél nagyobb fokszámú csúcshoz illesztjük:

Ekkor a sok fokú csúcs még több fokúvá válik, a hozzáadott csúcs pedig 1 fokú lesz. Vagyis f₁ nő eggyel, c viszont változatlan marad. Ezért az f₁ ≥ c+2 még inkább fennáll (f₁ > c+2)

Több lehetőség nincs, kész vagyunk.