Archiv diskusního fóra o matematice, 2006–2026
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é.)
Offline
↑ 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.
Offline
↑ 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.)
Offline
↑ 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 :)
Offline
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í.
Offline