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 alamgraafi, mis on puu ja sisaldab G kõiki tippe Kruskali algoritm vähima kaaluga aluspuu leidmiseks: o Valime graafist G vähima kaaluga serva k1 o Iga i=2, ..., n-1 korral valime graafist G sellise vähima kaaluga serva ki, mis erineb eelmistest ja ei moodusta nendega koos tsüklit Kruskali algoritmi korrektsus: o Algoritm töötab - 1 sammu, sest igal sammul leidub uus tingimusi rahuldav serv
topoloogiline isomorfism on kahe topoloogilise ruumi üksühene vastavus, teisendades säilitatakse objekti topoloogilised omadused. Kaks graafi G1 ja G2 on homöomorfsed, kui nad on mõlemad saadavad mingi graafi G' servasid poolitades. Näiteid homöomorfismidest: tass => kohver => sõõrik; Väga tuntud homöomorfism on ka nö. trefoil'i sõlm, mis on iseenesest samuti homöomorfne sõõrikuga. Kuratowski' teoreem: Graaf on tasandiline parajasti siis ja ainult siis, kui ta ei sisalda alamgraafi, mis oleks homömorfne kas graafiga K5 või K3,3. Teisisõnu, graaf G ei ole tasandiline parajasti siis, kui temas sisaldub K5 või K3,3 järgmiselt: 1). Graafi G tipud on K5 või K3,3 tippudeks. 2). Graafi G lihtahelad, mis ei lõiku (v.a. otstippudes) lihtahelate koosseisus sisalduvad tipud on sel juhul tekitatud serva poolitamise operatsiooniga(ning seega graafid on homoömorfsed) on K5 või K3,3 servadeks. K
annaabi.ee 
