Ore-tétel és Dirac tételről pár kérdés? Gràfelmélet!

Az Ore-tétel nem az, amit leírtál... Legfeljebb úgy, hogyha azt mondod, hogy a G gráf komplementerében nézed a szomszédos csúcsokat, és azok fokszámösszege kisebb a csúcsok számánál, akkor az eredetiben van Hamilton-kör.

Az n>=3 csúcsú teljes gráf komplementere az n darab izolált csúcsot tartalmazó gráf. Ebben igaz az, hogy bármely két szomszédos csúcs fokszámösszege kisebb n-nél (mivel 0 darab ilyen csúcspár van), így az eredeti gráfban van Hamilton-kör.

Ore: Ha az n pontú G egyszerű gráfban minden olyan

x, y ∈ V (G) pontpárra, amelyre x, y ̸∈ E(G) (nem szomszédosak), teljesül az, hogy d(x) + d(y) ≥ n, akkor

a gráfban van H-kör.

Dirac: Ha egy n pontú G egyszerű gráfban minden pont

foka legalább n/2, akkor a gráfban létezik H-kör.

Előfordulhat, hogy félremondta az előadó. Megesik.

Mindenesetre kérdezz rá, és tisztázd le; nem fog érte haragudni, sőt, még örülni is fog, hogy foglalkozol a témával.

Azért a csoporttársakat sem árt megkérdezni, hogy ők mit jegyzeteltek.