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).
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.
Graafi tipuga v intsidentsete servade arvu nimetatakse tipu v astmeks 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
annaabi.ee 
