The Postal Owl

Nerozumím dotazu, asi jsem to špatně napsal. Zkusím to zformulovat jasněji: Jakýkoliv podgraf tohoto grafu můžu vytvořit tak, že smažu vrcholy spolu s jejich hranami a k tomu můžu smazat ještě nějaké hrany navíc. Vytvořím tedy libovolný podgraf smazáním nějakých vrcholů a nějakých hran. Podle toho upravím i posloupnost $v_1,..., v_n$ odebráním smazaných vrcholů. Ona klíčová vlastnost, že každý vrchol sousedí s maximálně d vrcholy napravo, ale zůstane zachována, protože jsem zprava každého vrcholu jenom smazal vrcholy, příp. hrany, ale nic jsem nepřidal, žádného souseda jsem nikomu nepřidal. No a v každém podgrafu a tedy takovéto posloupnosti se stačí podívat na vrchol nejvíce vlevo, který musí pořád mít nanejvýš d-sousedů, takže stupeň d nebo menší. Proto je v každém podgrafu vrchol stupně nejvýše d a graf je d-degenerovaný.

Preview