a) Bizonyítsuk be, hogy minden 4-nél nagyobb n számra van olyan n csúcsú G gráf, hogy G-ben és a komplementerben is van Hamilton kör.
b) Egy 100 csúcsú egyszerű gráfban két nem szomszédos csúcs foka 49, az összes többi csúcs foka legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
c) Mit mondhatunk arról a 101 pontú gráfról, amiben minden csúcs foka legalább 50. Van-e a gráfban Hamilton út?
Adott egy 100 csúcsú egyszerű gráf, amiben két szomszédos csúcs foka 49, az összes többi csúcs foka pedig legalább 50. Bizonyítsuk be, hogy van a gráfban Hamilton út.
1001 pontú gráf minden csúcsa legalább 501 fokú, kivéve egyetlen csúcsot, aminek a fokszáma 500. Bizonyítsuk be, hogy a gráfban van Hamilton kör.
a) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid \leq 2 $.
Van-e $G$-nek olyan feszítőfája, hogy összes éle olyan, amelyre $ \mid x-y \mid = 2$ teljesül?
b) A $G$ egyszerű gráf csúcshalmaza legyen $V(G)=\{1, 2, \dots, 10 \}$. Az $x,y \in V(G)$, $x \neq y$ csúcsok pontosan akkor legyenek szomszédosak $G$-ben, ha $ \mid x - y \mid =2 $ vagy $\mid x-y \mid = 3$.
Van-e $G$-ben Hamilton út, illetve Hamilton kör?
a) Egy 100 csúcsú $G$ összefüggő gráf éleit az 1 és 2 súlyokkal súlyoztuk úgy, hogy az 1 súlyú élek részgráfja (vagyis az a gráf, melynek csúcsai azonosak $G$ csúcsaival, de annak csak az 1 súlyú éleit tartalmazza) 7 komponensből áll.
Határozzuk meg $G$ egy minimális összsúlyú feszítőfájának súlyát.
b) Egy 100 csúcsú összefüggő, egyszerű gráfnak 101 éle van. Mutassuk meg, hogy ekkor van a gráfban 3 páronként különböző feszítőfa. (Két feszítőfa akkor különböző, ha nem pontosan ugyanazon élek alkotják.)
