o Maksimaalne võimalik tipu aste n-tipulises graafis on n-1. Tipuastmete teoreem o Teoreem. Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. 32 o Tõestus. Iga serv suurendab oma kummagi otspunkti astet (ja seega ka astmete summat) kahe võrra. o Järeldus. Igas graafis on paaritu astmega tippe paarisarv. 35. Ahel, ahela otstipud ja sisetipud. Lihtahel. Teoreem lihtahelast. Kaugus. [2] Ahel, otstipud, sisetipud, lihtahel o DEF: Ahelaks nimetatakse graafi tippude järjendit v0, v1, …, vk, kus iga kaks järjestikust tippu on servaga ühendatud. o Tipud v0 ja vk on ahela otstipud, ülejäänud tipud on sisetipud. o Ahela servade arvu k nimetatakse ahela pikkuseks. o Ahel võib tippe ja servi sisaldada ka korduvalt. o Kui ahel ei sisalda korduvaid tippe ega servi, nimetatakse teda lihtahelaks. Teoreem lihtahelast o Teoreem
Regulaarseks graafiks nimetatakse graafi, mille kõigi tippude astmed on võrdsed Ahelaks nimetatakse graafi tippude järjendit v0, v1, ..., vk (k0), kus iga kaks järjestikust tippu on servaga ühendatud o Tipud v0 ja vk on ahela otstipud o Ülejäänud tipud on ahela sisetipud Teeks nimetatakse ahelat, kus ükski serv ei kordu Lihtahelaks nimetatakse ahelat, kus ükski tipp ega serv ei kordu Teoreem lihtahelast: kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v Tippude u ja v vaheliseks kauguseks nimetatakse tippude u ja v vahelise lühima lihtahela pikkust Kinniseks ahelaks nimetatakse ahelat, mis algab ja lõpeb samas tipus Tsükliks nimetatakse kinnist ahelat, kus on vähemalt üks serv ja ükski serv ei kordu Lihttsükliks nimetatakse tsüklit, kus iga sisetipp esineb ainult ühe korra
annaabi.ee 
