5. domácí úkol - MIN301 - podzim 2023 - odevzdat do 17.12.2023
Nechť G je graf, který je stromem, přičemž právě 14 jeho vrcholů má stupeň 1 a všechny ostatní vrcholy mají stupeň buď 4 nebo 5. Rozhodněte, zda takový graf existuje. Jestliže ano, popište kolik je takových grafů až na izomorfismus.
Řešení: Označme n\ počet vrcholů stupně 4 a n2 počet vrcholů stupně 5. Pak počet hran je |(4ni + 5n2 + 14). Jelikož G je strom, je počet hran také roven n\ + n2 + 14 — 1. Tedy i(4ni + 5n2 + 14) = m + n2 + 13, tj.
2tíi + 3n2 = 12,    rii,n2 G N0.
Tedy «2 je sudé a 0 < n2 < 4, tj. dostáváme tři možnosti:
Kn2) G {(0,4), (3, 2), (6,0)}.
Pro všechny tři případy existuje graf splňující zadané parametry. Při popisu všech možností stačí uvažovat jen podgraf z vrcholů stupně 4 a 5 (to bude zase strom) a určit počet možností pro tento podgraf. Pro {ni,n2) = (0,4) jsou dvě neizomorfní možnosti (=počet stromů na čtyřech vrcholech), pro {ni,n2) = (3,2) je patnáct neizomorfních možností (existují tři stromy na pěti vrcholech, ale je více způsobů, jak označit jeho vrcholy třemi čtyřkami a dvěma pětkami) a pro (rii,n2) = (6,0) je pět neizomorfních možností (počet stromů na šesti vrcholech je šest, ale "hvězdice"má v centru vrchol stupně 5). Celkem tedy máme 2 + 15 + 5 = 22 grafů až na izomorfismus.