Diskreetne matemaatika II - viies kodutöö
Tulemuseks saan graafi, millel on
(n-1) tippu ja (m-a) serva.
Eeldan, et väide kehtib saadud graafi korral, st et graafil (n-1) tipu ja (m-a) servaga on (n-1-m+a)
sidususkomponenti.
Nüüd lisan selle eemaldatud tipu t graafi tagasi selliselt, et tema aste oleks maksimaalselt a. See aga
tähendab, et ta on ühendatud maksimaalselt a graafi G sidususkomponendiga. Seega ühendab lisatud
tipp t omavahel maksimaalselt a graafi G sidususkomponenti, see tähendab, et maksimaalselt a
sidususkomponendi asemel saan ma ühe sidususkomponendi, sest sidususkomponendi puhul on
tegemist maksimaalse sidusa alamgraafiga.
Diskreetne matemaatika II Kodused ülesanded 5 Olga Dalton
104493
IAPB21
annaabi.ee 
