Vonalak, utak, körök

Feladat: Az alábbi rajzok egy-egy lakás alaprajzát mutatja, ahol a leíró gráf minden élén egy-egy ajtó van. Be lehet-e járni a lakást úgy, hogy minden ajtón pontosan egyszer haladunk át?
 

Feladat: Egy irányított gráfban van zárt ir'anyított Euler-vonal (olyan irányított séta, amely minden élen pontosan egyszer halad át és minden pontot érint, továbbá kezdõpontja egybeesik végpontjával). Bizonyítsuk be, hogy gráfunk erõsen összefüggõ, továbbá minden pontjában a befok egyenlõ a kifokkal.

Feladat: ^* Bizonyítsuk be, hogy egy irányított gráfban akkor és csak akkor van zárt irányított Euler-vonal, ha erõsen összefüggõ és minden pontjában a befok megegyezik a kifokkal.

Feladat: Bizonyítsuk be, hogy egy irányított gráfban akkor és csak akkor van nyilt (nem zárt) irányított Euler-vonal, ha erõsen összefüggõ és minden pontjában a befok megegyezik a kifokkal kivéve kettõ pontot, amelyek közül az egyikben a befok eggyel több mint a kifok, míg a másikban eggyel kevesebb.

Feladat: ^* Egy körlapot felosztunk 2ⁿ darab egyenlõ szektorra. Majd egy forgatható fedõlapot rakunk rá, amely letakarja a körlapot, kivéve n szomszédos szektort, amelyet egy ablakon keresztül láttat. A fedõlap forgatásával bármely szomszédos szektor-n-es láthatóvá tehetõ, így az ablaknak 2ⁿ darab lehetséges állása van. Bizonyítsuk be, hogy beírhatunk a szektorok mindegyikébe egy 1-es vagy egy 0-s számjegyet úgy, hogy az ablak összes lehetséges állásában az óramutató járása szerint elolvasva a látható biteket az összes 2ⁿ n hosszú bitsorozatot láthassuk (persze szükségszerûen mindegyiket pontosan egyszer).  

Feladat: Egy egyszerû gráf minden pontjának foka legalább d. Bizonyítsuk be, hogy a gráfban van d hosszú út.

Feladat: Egy egyszerû gráf minden pontjának foka legalább d. Bizonyítsuk be, hogy a gráfban van legalább d hosszú kör.

Feladat: Döntsük el, hogy az alábbi gráfokban van-e Hamilton-kör.
 

Feladat: A 9 pontú teljes gráf éleit színezzük ki négy színnel úgy, hogy minden szín egy-egy Hamilton-kör élhalmazát adja ki.

Feladat:

• Rajzoljuk fel azt az egyszerû gráfot, amely csúcsai az {1,2,3,4} halmaz kételemû részhalmazai és kettõ pontosan akkor van összekötve, ha metszetük egyelemû. Van-e Hamilton-kör az így kapott gráfban?
• Rajzoljuk fel azt az egyszerû gráfot, amely csúcsai az {1,2,3,4,5} halmaz kételemû részhalmazai és kettõ pontosan akkor van összekötve, ha metszetük egyelemû. Van-e Hamilton-kör az így kapott gráfban?
• Rajzoljuk fel azt az egyszerû gráfot, amely csúcsai az {1,2,3,4,5} halmaz háromelemû részhalmazai és kettõ pontosan akkor van összekötve, ha metszetük kételemû. Van-e Hamilton-kör az így kapott gráfban?
• Rajzoljuk fel azt az egyszerû gráfot, amely csúcsai az {1,2,3,4,5,6} halmaz háromelemû részhalmazai és kettõ pontosan akkor van összekötve, ha metszetük egyelemû. Van-e Hamilton-kör az így kapott gráfban?
• ^* Legyen G az az egyszerû gráf, amely csúcsai az {1,2,...,n-1,n} halmaz k-elemû részhalmazai és kettõ pontosan akkor van összekötve, ha metszetük m-elemû (0 < m < n). Bizonyítsuk be, hogy a kapott gráfban van Hamilton-kör.