tegemist maksimaalse sidusa alamgraafiga. Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton 104493 IAPB21 Seega, kui enne eeldasin, et graafil (n-1) tipu ja (m-a) servaga on (n-1-m+a) sidususkomponenti, siis tipu t tagasi lisamine teeb sidususkomponentide arvu maksimaalselt (a-1) võrra väiksemaks. Seega on mul nüüd: n 1 m + a (a 1) = n 1 m + a a + 1 = n m sidususkomponenti, mida tuligi näidata. ÜLESANNE 5. Tähistan selle tipu t-ga. Tema aste on siis ülesande tingimuste järgi d. Kui ma kustutan tipu t, siis jääb mul järele d sidususkomponenti, millest igaüks on kas üksik tipp või puu, millel on vähemalt 2 lehte.
Graafi tahud- graafi joonis tükeldab alati tasandi. Tekkinud tükke nimetatakse G tahkudeks. Graafil leidub alati ka üks lõpmatu tahk (sisuliselt tahk, mis ümbritseb kogu graafi). Euleri valem(id): Teoreem: Olgu graaf G sidus tasandiline graaf, mille tippude arv on n, servade arv m ning joonise tahkude arv f. Sellisel juhul kehtib alati n + f = m + 2 ehk n + f m = 2. a). Järeldus 1: Olgu G tasandiline graaf, mille sidususkomponentide arv on k, tippude arv on n, servade arv on m ning joonise tahkude arv f. Sellisel juhul kehtib alati n + f = m + k + 1. b). Järeldus 2: Olgu G sidus tasandiline graaf. Kui tal on vähemalt 3 tippu e. n = 3, siis kehtib alati m 3n 6, kus n tähistab tippude arvu, m servade arvu. c). Järeldus 3: Täielik graaf K5 ei ole tasandiline, eelmise järelduse põhjal (n=5,m=10). d). Järeldus 4: Kui G on sidus tasandiline, vähemalt 3 tipuga lihtgraaf, milles pole
annaabi.ee 
