# Domácí úkol 5.6 - degd
Začneme s grafem $|V| = 2, d = 0$. Zde očividně existuje cesta délky $1$ (vrchol samotný).
Pro $d = 1$ musí být oba vrcholy spojené, takže existuje cesta délky $2$. To jsou všechny možnosti pro $2$ vrcholy.
Přidáme-li nyní další vrchol, pak mohou nastat tři možnosti:
- Vrchol není spojený s některým z předchozím. Pak se stupeň některého z vrcholů nezvětší, nemusíme tedy hledat novou cestu.
- Vrchol je spojen s $d$ ostatními vrcholy. Pak se stupeň všech těchto vrcholů zvýší o $1$, takže musíme dokázat, že se naše cesta prodloužila o jeden vrchol. To je ovšem snadné, jelikož nový vrchol je spojen se všemi předchozími, musí být spojen i s posledním vrcholem naší původní cesty.