A G gráf csúcsai az n hosszúságú 0-1 sorozatok, és két csúcs között akkor megy él, ha a megfelelő sorozatok pontosan egy helyen térnek el egymástól. Mely n-re van a) Euler-vonal; b) Hamilton-kör G-ben?

a) a G gráf k reguláris és Euler tétel: "Egy összefüggő G gráfban akkor és csak akkor létezik Euler-kör, ha minden csúcsának fokszáma páros.", tehát akkor és csak akkor létezik Euler-kör, ha k páros

ha Euler-vonal alatt Euler sétát értesz, akkor egyetlen esetben sem, mivel k reguláris és 2 pont kivételével az összesnek párosnak kéne lennie a 2pontnak pedig kötelezően páratlannak

Egyébként szokták Euler-sétának nevezni, mert egészen pontosan definiálva egy sétáról van szó, de ennek ellenére Euler-útnak is nevezik, ha ugyan onnan indul ahol végződik, akkor Euler-kör, Euler-vonal kivejezést eddig még nem hallottam :\

b) Hamilton-kör mindig van, ezt legegyszerűbben egy példa konstruálással lehet bizonyítani (máshogy nem is NP teljes a feladat):

a példát teljes indukcióval fogom felépíteni, k=1 esetén a (0),(1) egy Hamilton kör

k=2 esetén a sorozat első száma 0 és felhasználom a k=1 esetben leírt Hamilton kört (00),(01) majd azt első 0-át 1-re változtatom és a k=1-nél felírt Hamilton körön elindulok visszafelé tehát (11),(10)

így k=2-re (00),(01),(11),(10)-t kapok, ami Hamilton kör

k=3-ra k=2-t felhasználva ugyan így: (000),(001),(011),(010) majd elindulok visszafelé: (110),(111),(101),(100)

k=n-nél k=n-1-et felhasználva konstruálható a Hamilton kör

ebből világos, hogy minden k-re létezik.

bizonyítás: tényleg mindig egy számot változtatok: 1 esetén igaz, 2 esetén igaz, k esetén visszavezethető k-1-re, mert amikor 0-át 1-re változtatom, csak egy számot változtatok, és amikor visszafelé indulok, akkor nem sérül az állítás

mindig Hamilton kört kapok, 1 esetén nem hagytam ki semmit, 2 esetén sem, k esetén szintén visszavezethető k-1-re