Hogyan bizonyítanátok teljes indukcióval?

Állítás: Az n csúcsú fa éleinek száma n-1.

Bizonyítás: A pontok száma szerinti teljes indukcióval.

Az egy csúcsú fa éleinek száma nulla.

Tegyük fel, hogy a k csúcsú fa éleinek számáról tudjuk, hogy k-1.

Vegyünk most egy k+1 csúcsú fát. Ebben a fában biztosan van elsőfokú csúcs (különben lenne benne kör - egy másik tétel miatt) Hagyjuk el ezt a pontot a rá illeszkedő éllel együtt. Ekkor egy k pontból álló, továbbra is összefüggő, körmentes gráfot, azaz fát kapunk. Mivel ennek k-1 éle kell legyen az indukciós feltevés miatt, így a k+1 csúcsú fának eggyel több, azaz k éle volt.