The Postal Owl

Pokud lze
>  uspořádat vrcholy do sekvence $v_1, \dots, v_n$ takové, že, pro každé $i=1,\dots,n$, $v_i$ má v $G[\{v_i, v_{i+1}, \dots, v_n\}]$ nanejvýš $d$ sousedů, pak je $G$ $d$-degenerovaný. (Tzn. "otrhatelnost" vrcholy stupně nanejvýš $d$ je ekvivalentní s $d$-degenerovaností.)

$d$-degenerovanost jsme definovali tak, že každý podgraf obsahuje vrchol stupně $d$ nebo menší.

Podívejme se na vrcholy libovolného podgrafu. Konkrétně je seřaďme stejně jako v původním grafu. To, co platilo v původním uspořádání, musí platit i v novém, a sice že každý vrchol má nanejvýš $d$ sousedů napravo od něj, protože žádné nové hrany nepřibyly. Teď se stačí podívat na vrchol, který v našem uspořádání zbyl nejvíce vlevo: ten má nejvýše $d$ sousedů napravo (dle předpokladu uspořádání) a nalevo od něj žádný vrchol není, tudíž má nejvýše $d$ sousedů celkem, a tudíž je podgraf také $d$-degenerovaný.

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ý.