Matematické Fórum

check_drummer · 20. 03. 2019 09:02

Ahoj, ve svých poznámkách jsem našel: Nechť K je maximální graf (vzhledem k počtu hran) takový, že neobsahuje úplný podgraf na p vrcholech (p je pevné). Dokažte (nebo vyvraťte), že v K neexistují tři vrcholy z nichž nejvýše dva jsou spojeny hranou. (Můžete předpokládat, že p je dostatečně velké.)

laszky · 20. 03. 2019 21:55

↑ check_drummer:

Ahoj. Necht u,v,w jsou tri vrcholy grafu K takove, ze hrana je pouze mezi uv. Necht Q je mnozina libovolnych jinych p-3 vrcholu. Oznacme G podgraf grafu K indukovany mnozinou vrcholu {u,v,w} ∪ Q. Graf G je tvoren p vrcholy, ale pridanim hrany mezi uw nebo vw nevznikne uplny graf na p vrcholech (jedna hrana bude urcite chybet). Tim ziskame spor s predpokladanou maximalitou grafu. Analogicky pro pripad, kdy u,v,w tvori nezavislou mnozinu (nesou vubec spojeny). V K tudiz neexistuji tri vrcholy z nichz nejvyse dva jsou spojeny hranou.

check_drummer · 20. 03. 2019 23:23

↑ laszky:
Ahoj. A co když existuje nějakých p-2 vrcholů takových, že spolu s vrcholy u,w a přidáním hrany uw již vznikne úplný podgraf velikosti p? (A totéž pro hranu vw.)

laszky · 21. 03. 2019 18:01 — Editoval laszky (21. 03. 2019 22:38)

↑ check_drummer:

Ahoj, mas pravdu. Treba petiuhelnik (C5) je maximalni graf neobsahujici trojuhelnik (K3), pricemz v nem existuji trojice takove, ze jen dva vrcholy jsou spojeny. Pro ostatni zatim netusim :)

check_drummer · 21. 03. 2019 21:40

Ahoj, namísto

laszky napsal(a):
... pricemz v nem existuji trojice takove, ze jen dva vrcholy jsou spojeny.

by tam spíš mělo stát:
... pricemz v nem existuji trojice takové, že alespoň dvě dvojice vrcholů jsou spojeny.

Protože jestli to chápu dobře, tak pro p=3 tvrzení neplatí.

Matematické Fórum

#1 20. 03. 2019 09:02

Maximální graf

#2 20. 03. 2019 21:55

Re: Maximální graf

#3 20. 03. 2019 23:23

Re: Maximální graf

#4 21. 03. 2019 18:01 — Editoval laszky (21. 03. 2019 22:38)

Re: Maximální graf

#5 21. 03. 2019 21:40

Re: Maximální graf

laszky napsal(a):

Zápatí