A Dirac-tétel azt mondja ki, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor a gráfban van Hamilton kör.
A Dirac-tétel azt mondja ki, hogy ha egy $G$ egyszerű, $n \geq 3$ csúcsú gráfban minden csúcs foka legalább $\frac{n}{2}$, akkor a gráfban van Hamilton kör.
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?
