Alapkérdés: Legyen G egy n pontú egyszerű gráf, amely nem tartalmaz négy hosszú kört. Milyen sok éle lehet G-nek?
Nevezzük cseresznyének a G gráf két élet, ha közös végpontban futnak össze (a két él legyen e=xy és f=xz). Az x csúcsot a cseresznye közepének, y-t és z-t a cseresznye két szemének nevezzük. Egy látszólag új, az előzőektől független kérdést teszünk fel. Az erre adott válaszok azonben elvezetnek eredeti kérdésünk megválaszolásához.
A G-beli cseresznyéket először közepüknél számoljuk össze. Egy x csúcshoz (d(x)2) darab cseresznye van, amleyek közepe x. Valóban az x közepű cseresznyék két élét az x-re illeszkedő d(x) darab él közül tetszőleges kettő alkothatja. Azaz ahhoz, hogy a cseresznyék számát megkapjuk a (d(x)2) számokat kell összegezni az összes x csúcsra.
Egy másik elindulás lehet a szemek csúcspárjai serint csoportosítani a cseresznyéket és ezen csoportosítás segítségével számolni meg azokat. (n2) darab lehetőség van a szempárokra. Ezen lehetőségek mindegyike mögött nulla vagy egy cseresznye van. Valóban, ha egy szempárhoz két (vagy több) cseresznye tartozna, akkor G-ben kialakulna egy négy hosszú kör, ami nem lehetséges. Így kapjuk, hogy a cseresznyék száma legfeljebb (n2).
A két gondolat összevetéséból kapjuk, hogy ha G csúcshalmaza {v1,v2,...,vn}, akkor (n2)>= (d(v1)2)+(d(v2)2)+ (d(v3)2)+...+(d(vn)2).
A jobb oldal alúlról becsülhető a Jensen-egyenlőtlenséget a (x2)=x(x-1)/2 konkáv függvényre alkalmazva:
Tétel: (Kővári Tamás,
T. Sós Vera,
Turán Pál)
Ha egy n pontú egyszerű gráf nem tartalmaz négy hosszú kört,
akkor |E|<=1/2·n3/2+1/4·n.
A fenti tétel felső becslést ad ext(n;C4)-re. Alsó becslést egy n pontú egyszerű gráf konstruálásával adhatunk, amely gráf nem tartalmaz négy hosszú kört, de ``sok'' éle van. A konstrukcióban szereplő élszám alúlról becsüli ext(n;C4)-t. A következő `feladat' ahhoz ad segítséget, hogy nyerhetünk a fenti felső becsléssel aszimptotikusan azonos alsó becslést:
Legyen padott prím és tekintsük az (x,y) egész számpárokat mod p. Készítsül el azt a gráfot, amelynek csúcsai ezek a párok, és két csúcs, (x,y) és (x',y') között pontosan akkor halad él, ha x·x'+y·y'=1 mod p. Az ily módon esetleg létrejövő hurokéleket hagyjuk el a gráfból. Az így kapott gráf nem tartalmaz négy hosszú kört.