Gráfelméletes feladat? (Van elképzelésem a megoldásokról, de egyáltalán nem vagyok bennük biztos)

Hamilton-kört keresel. Az első eset igazolható a Dirac-tétellel, mert a csúcsok száma 12, és a fokok száma legalább 12/2=6. Tehát le tudnak ülni.

A második eset. Tegyük fel, hogy már leültek az asztal mellé. Jön az ipse. Ekkor állítom, hogy van olyan két szomszédos ember, akiket ismer az ipse. Közéjük le tud ülni.

Miért? Ez skatulyalevvel adódik. Indulj el valamilyen irányban karikázd be párosával a szomszédokat. Kapsz 6 párt. De az ipse legalább 7 embert ismer. Tehát van olyan páros, aminek mindkét tagját ismeri. Kész.

Magyarán az a kérdés, hogy van-e Hamilton-kör a gráfban.

a) Ha jól rémlik, akkor van egy olyan tétel, hogy ha minden csúcs foka legalább n/2, ahol n a csúcsok száma, akkor a gráfban van Hamilton-kör. Rövid utánanézés után meg is találtam a tételt, ez a Dirac-tétel. Mivel minden csúcs fokszáma 6, és 12/6=6<=6, ezért teljesül a Dirac-tétel.

b) Ültessük le az embereket megfelelően. Megérkezik András és "állítsuk fel az asztalra", majd kössük össze őt az ismerőseivel. Mivel 7 ismerőse van, ezért 7 élt húzunk be a gráfba. Ha két egymás mellett ülő emberhez be tudunk húzni egy-egy ismertségi élt, akkor azon ismerősei közé be tudjuk ültetni Andrást. A jelen felállásban neked azt kell megmutatnod, hogy ez mindig sikerülni fog. Azért nem írom le a megoldást, mert azt kérted, hogy ne írjam le.