Az Ore-tétel azt mondja, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban bármely $V_1$ és $V_j$ nem szomszédos csúcsra $d(V_i) + d(V_j) \geq n$ teljesül, akkor a gráfban van Hamilton kör.
Az Ore-tétel egy feltétel Hamilton kör létezésére.
1.
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?
