Diskreetse matemaatika elemendid
) koos temaga intsidentse servaga.
• Järele jääb k-tipuline puu (miks puu?), tema servade arv on induktsiooni eelduse
põhjal k - 1. Seega on esialgse graafi servade arv k.
• Järeldus. Tõestuses kirjeldatud sammude abil (lehte koos temaga intsidentse
servaga kustutades) võib igast puust jõuda 1-tipulise graafini.
Puu konstrueerimine
o Iga puu saab konstrueerida järgmisel viisil.
• Alustame 1-tipulisest graafist.
• Igal sammul lisame ühe tipu ja ühendame ta mingi olemasoleva tipuga.
45. Tarvilikud ja piisavad tingimused, et graaf oleks puu.
[2]
o Teoreem 3. Kui G on graaf, siis on järgmised väited samaväärsed.
1. G on puu
38
2. G on sidus, kuid ükskõik millise serva kustutamisel muutub mittesidusaks
3. G ei sisalda tsükleid, kuid ükskõik millise serva lisamisel tekib tsükkel
46
annaabi.ee 
