Santa Claus — 2021-11-20 21:40 (410 days ago) — edit — reply
Uvažme nejdelší podgraf cesty na daném grafu. Sporem: Pokud je tato cesta na $d$ nebo méně vrcholech, můžeme vzít jeden z jejich koncových vrcholů. Z jeho alespoň $d$ sousedících vrcholů se na cestě vyskytuje maximálně $d - 1$ vrcholů, protože cesta je na $d$ nebo méně vrcholech a jeden z těchto vrcholů je zvolený koncový vrchol, který se sebou nemůže sousedit. Potom ale alespoň jeden ze sousedících vrcholů není v nejdelší cestě obsažen a mohli bychom cestu o vrchol rozšířit, cesta tedy není nejdelší, což je spor. Z toho plyne, že nejdelší cesta bude délky alespoň $d+1$, a protože každý graf nutně cestu obsahuje* - třeba jednovrcholovou, bude v každém grafu obsažena také cesta na alespoň $d+1$ vrcholech, z níž můžeme cestu na právě $d+1$ vrcholech získat jako podgraf. *Výjimku snad tvoří prázdný graf, který neobsahuje žádný vrchol, tedy ani žádnou cestu, přestože splňuje podmínku, že každý jeho vrchol má stupeň alespoň $d$. Pro tento graf tvrzení neplatí, pokud za $d$ nezvolíme $-1$, pak bude cesta na nula vrcholech jeho podgrafem, protože se bude jednat také o prázdný graf (asi).