Matematické Fórum

Zdravím,

není to tak náročné jak to vypadá:

Nechť máme graf G (dle daných podmínek) a v něm cestu P tak, že její délka je maximálně d (taková musí existovat minimálně pro délku 1). Nyní si označme v poslední vrchol cesty. Tento vrchol má minimálně d sousedních vrcholů (spojených hranou), ale nejvýše d-1 je jich v cestě P. To znemená, že existuje vrchol (označme si jej v'), který je možné přidat k P, tak že nám vznikne cesta P' která je o jeden vrchol delší než P.

No a nyní jsou dvě možnosti: buď má P' délku d+1 a jsme hotovi, nebo má délku maximálně d a můžeme postup opakovat.