tipupaarid. Def: Graaf on paar (V,E), kus V on mittetühi hulk ning E hulk, mille elementideks on hulga V kaheelemendilised alamhulgad. Näide lk 47 (Palm) Tipu aste tipust väljuvate servade arv. Teoreem: Igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega. Järeldus: Igas graafis on paaritu astemga tippe paarisarv. Ahel graafis tippude järjend, kus iga kaks järjestikust tippu on servaga ühendatud (esimene ja viimane on otstipud vahepeal sisetipud). Ahela pikkus on k kui selles on k+1 tippu. Ahel võib läbida mõnda tippu mitu korda. Lihtahel kõik tipud läbitakse üks kord. Tippude u ja v vaheline kaugus - tippude u ja v vahelise lihtahela pikkus Tsükkel ahel mis lõpeb samas tipus kus algab. Sidus graaf iga kahe tipu vahel leidub ahel. Euleri tsükkel tsükkel mis läbib kõik graafi servad täpselt üks kord. (graaf euleri graaf).
Tipuastmete teoreem: igas graafis on kõigi tippude astmete summa võrdne servade arvu kahekordsega o Järeldus: igas graafis on paaritu astmega tippe paarisarv 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
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.
c. Järeldus. Igas graafis on paaritu astmega tippe paarisarv. c.i. Tõestus. Selleks, et kõigi tippude astmete summa tuleks paarisarv, peab summas esinema paarisarv paaritut liidetavat. 33) a. Ahel graafis G on selline tippude järjend v0, v1, ..., vk, kus iga kaks järjestikust tippu on servaga ühendatud. Tippe v0 ja vk nimetatakse ahela otstippudeks, ahela ülejäänud tipud v1, ..., vk-1 on sisetipud. b. Kui kõik ahela tipud on erinevad, siis nimetatakse ahelat lihtahelaks. c. Teoreem. Kui graafis G leidub ahel tipust u tippu v, siis leidub graafis G ka lihtahel tipust u tippu v. c.i. Tõestus. https://moodle.ut.ee/mod/url/view.php?id=107318 lk 52. d. Tippude u ja v vahelise lühima lihtahela pikkust nimetatakse tippude u ja v kauguseks. 34) a. Ahelat, mis lõpeb samas tipus, kus algab, nimetatakse tsükliks. b
annaabi.ee 
