Feladat: 2.27.
a) Most azt akarjuk bebizonyítani, hogy egy húszpontú gráf már akkor is tartalmaz
C4
-et, ha az
átlagfokszám legalább öt. Keressük meg, hogy melyik ponton akad el a
2.25. bizonyítása.
b) A
K.II.10.3. feladat felhasználásával válaszoljunk a következő kérdésre: Adott egy egyszerű (véges) gráf. Összeadjuk minden csúcsra a szomszédjaiból képezhető pontpárok számát. Hogyan becsülhető alulról ez az összeg az élszámmal (és a pontszámmal)?
Hogyan becsülhető ez az összeg felülről a pontszám segítségével, ha a gráfban nincs négypontú kör?
c) Bizonyítsuk be, hogy ha egy húszpontú egyszerű gráfnak legalább 50 éle van - azaz az átlagfokszáma legalább öt -, akkor van benne négypontú kör.
Megoldás: 2.27
a) Ha ismét hozzárendeljük minden csúcshoz a ,,szomszédsági" halmazát, azaz a vele összekötött pontok halmazát, akkor továbbra is igaz, hogy ha ezek között van kettő, aminek legalább két közös pontja van, akkor (és csak akkor) van
C4
a gráfban. A
2.25. feladat megoldásában azt használtuk, hogy ha minden halmaz legalább ötelemű, és semelyik kettőnek nincs két közös pontja, akkor nem lehet belőlük húsz darab, legfeljebb 19, és ez ellentmondás. Csakhogy most lehetnek két, három vagy négyelemű halmazok is, és ezek kevés pontpárt fednek le, tehát elképzelhető, hogy több ilyen halmaz van.
b) Egy-egy ilyen szomszédsági halmaz
(
di
2
-
di
)/2 párt fed le (
di
-vel jelölve az
i-edik csúcs fokszámát), tehát az összesen lefedett pontpárok száma
∑1≤i≤n
di
2
/2-
∑1≤i≤n
di
)/2.
|
A b) feladat erre a kifejezésre kér alsó és felső becslést. Itt a második összeg az élszám,
e. Az első összeg pedig a
K.II.10.3. feladat szerint legfeljebb
2
e2
/n. A keresett alsó becslés tehát
2
e2
/n-e. Egyenlőség csak reguláris gráfra áll fenn.
1. megjegyzés. Ez az a lépés, amivel sikerült az a)-ban jelzett nehézséget áthidalni. Lényegében beláttuk, hogy ha a fokszám nem egyenletes, akkor ,,rosszabb" a helyzet, mintha a fokszám egyenletes. Most már alkalmazhatjuk a
2.25. feladat megoldásának gondolatmenetét!
Ha a gráfban nincs négypontú kör, akkor ebben az összegben minden pontpárt legfeljebb egyszer számoltunk meg. Tehát a teljes gráf élszáma a felső becslés:
n(n-1)/2.
c) Legyen tehát
G egy húszpontú gráf, amelyben nincsen kör. Vessük össze a b)-ben kapott két becslést. Az élszámra,
e-re a következő egyenlőtlenséget kapjuk:
e2
/10-e≤190.
Ez pedig
e≥50-re nem teljesül. Tehát egy 20 pontú és legalább 50 élű gráfban van
C4
.