Vaatleme mingit k+1 tipuga puud. Kustutame ühe lehe koos temaga intsidentse servaga. Järele jääb k-tipuline puu, tema servade arv on induktsiooni eelduse põhjal k-1. Seega on esialgse graafi servade arv k. Tarvilikud ja piisavad tingimused, et graaf G oleks puu: o G on sidus, kuid ükskõik millise serva kustutamisel muutub mittesidusaks o G ei sisalda tsükleid, kuid ükskõik millise serva lisamisel tekib tsükkel Puu tingimus lihtahelate kaudu: Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel Algoritmi F korrektsuse teoreem: [Sisend rahuldab eeltingimusi () Algoritm F lõpetab töö ja tulemus = () rahuldab järeltingimust (, )] Sidusa graafi G toespuuks e. Aluspuuks nimetatakse G sellist
c). Puus leidub alati n-1 serva, kus n on tippude arv. d). Iga puu koosseisus leiduv serv on sild. e). Suvalise serva lisamisel mistahes kahe puu tipu vahele tekib tsükkel. f). Suvalise kahe tipu vahel leidub alati täpselt 1 lihtahel. Mets- graaf, mis ei sisalda tsükleid (ent ei pruugi olla ka sidus). Lehed- Lehed on puu tipud, mille astmeks on 1 (e. deg(e) = 1). Sild- Sidusa graafi G=(V,E) serva e E nimetatakase sillaks, kui selle serva eemaldamisel muutuks graaf mittesidusaks. Rakenduses esineb sageli ka juurega puid st. tippude hulgast on välja eraldatud üks tipp, juur. Serva seda otstippu, mis asub juurele lähemal, nimetatakse sellisel juhul ülemtipuks, teist otstippu aga alamtipuks. [34]. Graafi vähima kaaluga aluspuud. Graafi aluspuu- sidusa graafi G aluspuu on vähima servade arvuga alamgraaf, mis ühendab kõiki graafi tippe. Cayley teoreemist järeldub, et igal n-tipuliselt täisgraafil on kokku nn-2 erinevat aluspuud.
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. Puu tingimus lihtahelate kaudu. [2] o Teoreem. Graaf G on puu parajasti siis, kui tema iga kahte erinevat tippu ühendab täpselt üks lihtahel. o Tõestus. Tarvilikkus. Olgu G puu. Et puu on sidus, siis G iga kahte tippu u ja v ühendab vähemalt üks lihtahel. Kahte lihtahelat u ja v vahel olla ei saa, sest siis
annaabi.ee 
