ITT0030 Diskreetne matemaatika II - eksamikonspekt
Järeldus 5: Täielik kahealuseline graaf K3,3 ei ole tasandiline (tuleneb eelmisest
omadusest, kuna graafis K3,3 on n = 6 ning m = 9.
f). Järeldus 6: Iga tasandilises lihtgraafis leidub tipp, mille asta on ülimalt 5 pea
tähtsaim omadus. Tähendab seda, et ei saa eksisteerida tasandilist lihtgraafi, mille kõikide
tippude aste oleks >5 (vastasel juhul ei saa ta olla tasandiline).
(K5 ja K3,3 on meile niivõrd tähtsad seetõttu, et IGA mittetasandiline graaf sisaldab ÜHTE
neist alamgraafina).
Euleri valem on väga tähtis, kuna ta võimaldab meil mistahes graafi G kohta välja selgitada,
kas viimane on tasandiline (e. kas ta on tasandil esitatav selliselt, et mistahes 2 serva ei
lõikuks).
[41]. Graafi tasandilisuse kriteeriumid. Kuratowski teoreem.
Graafi tasandilisuse kriteeriumid panevad kõige täpsemini paika Kuratowski ja Wagner:
Homöomorfism e. topoloogiline isomorfism on kahe topoloogilise ruumi üksühene
annaabi.ee 
