Skóre
Úloha číslo: 3668
Posloupnost \((1{,}1,2{,}2,2{,}4)\)
- není skóre grafu;
- je skóre grafu, ten může být i nesouvislý;
- je skóre grafu, ten musí být souvislý.
Řešení
Pokud ke čtyřcyklu přidáme dva listy, dostaneme jeden z možných grafů s uvedeným skóre.
Alternativně lze ověřit, že jde o skóre grafu pomocí věty o skóre: \((1{,}1,2{,}2,2{,}4)\to(1{,}0,1{,}1,1)\to(0{,}1,1{,}1,1)\to(0{,}1,1{,}0)\to(0{,}0,1{,}1)\to(0{,}0,0)\)
Kdyby graf měl být nesouvislý, pak ta komponenta, co obsahuje vrchol stupně 4, musí mít alespoň 5 vrcholů. Graf nemá izolované vrcholy, takže každá komponenta má alespoň dva vrcholy. Dohromady máme ale 6 vrcholů na nichž komponenty uvedených velikostí: alespoň 5 a alespoň 2, vystavět nelze.
Odpověď
Správná odpověď je c.