Legyen 1<k<n. G gráf csúcsai v1, v2, . , vn, bármegy 1<=i<j<=n esetén vi és vj össze van kötve, ha k<j. Határozzuk meg, hogy milyen n, k párokra lesz G-ben Hamilton út. Írok egy megoldást, valaki el tudná magyarázni érthetőbben?

A megoldókulcs szerinti megoldás:

Legyen n páros. Ha k ≤ n/2, akkor a v1vnv2vn−1v3 · · · vn−k+2vk út, kiegészítve a megmaradó vk+1, . . . , vn−k+1

csúcsokon át vezető úttal, egy Hamilton utat ad. 2 pont

Ha viszont k ≥ n/2 + 1, akkor k ≥ n − k + 2. Hagyjuk el a gráfból a vk+1, . . . , vn csúcsokat, a megmaradó v1 . . . , vk

csúcsok között nem vezet él. Így n − k csúcs elhagyásával k ≥ n − k + 2 komponensre esett szét a gráf, ami azt jelenti,

hogy nem tartalmaz Hamilton utat. 2 pont

Most tegyük fel, hogy n páratlan. Ha k ≤ (n + 1)/2, akkor a v1vnv2vn−1v3 · · · vn−k+2vk út, kiegészítve az esetlegesen

megmaradó vk+1, . . . , vn−k+1 csúcsokon át vezető úttal, egy Hamilton utat ad. 2 pont

Ha viszont k ≥ (n + 3)/2, akkor k ≥ n − k + 3. Hagyjuk el a gráfból a vk+1, . . . , vn csúcsokat, a megmaradó v1 . . . , vk

csúcsok között nem vezet él. ´Igy n − k csúcs elhagyásával k ≥ n − k + 3 komponensre esett szét a gráf, ami azt jelenti,

hogy nem tartalmaz Hamilton utat. 2 pont

Osszefoglalva, akkor és csak akkor van Hamilton út, ha ¨ k ≤ ⌈n/2⌉