Rajzolható-e olyan ötpontú egyszerű gráf?

Legyen egy n csúcsú (létező egyszerű) gráf fokszámai a(1)>=a(2)>=...>=a(n), és nevezzük {a(1);a(2);...;a(k)} fokszámokkal rendelkező csúcsok halmazát nagy fokszámú csúcsok halmazának:=N, a többi a kis fokszámú csúcsok halmazát:=K jelölje. Ebben az esetben ha N-ben futó maximális élszám e(N), a két halmaz között futó élek száma e(N;K), akkor tetszőleges k-ra (1<=k<=n) e(N)+e(N;K)<=(a(1)+a(2)+...+a(n))/2, vagyis N-ben és N és K között futó élek száma legfeljebb annyi, mint az élek száma. Ha létezik k, hogy ez nem teljesül, akkor a számsorhoz nem létezik gráf (ez az ellenpélda, amit mondtam).

Ez a tétel használható a d) feladatban; ha k=3, akkor a nagy fokszámok: (3;4;5), ezek között legfeljebb 3 él futhat, a két ponthalmaz között legfeljebb 4 él futhat, tehát legfeljebb 7 élt tudunk behúzni a gráfba, viszont (5+4+3+3+1)/2=8 élünk van, tehát erre a számsorra nem létezik gráf (persze, az egyszerűbb, hogy az 5-ösből legfeljebb 4 élt tudunk húzni a másik négybe, és ezért nem nyerő ez a számsor, de bonyolultabb esetben ezt és így kell használni).

Remélem, sikerült meggyőznöm a nagyérdeműt.

Ilyen kis fokszámoknál (de ez is általánosítható) a legmagasabb fokszámból érdemes kiindulni. Egy ötpontú egyszerű gráfban egy csúcs maximális foka négy (ez a d)-t kivégzi). A b) feladatban tekintsük azt a G' gráfot amiből a 4 fokszámú csúcsot és a belőle vezető éleket töröltük. Mivel minden ponttal össze volt kötve, minden csúcsnak eggyel csökken a fokszáma, 0,0,1,1 . A G' gráf tehát egyszerűen egy él és két pont. Addjunk hozzá egy ötödik pontot ami mind a négy ponttal össze van kötve, ez a keresett G gráf. Még az érettségiben is volt ilyen példa. Leírni tovább tart mint kigondolni :)

c) az páratlan, d) az 5 miatt nem lehet.

Az a) nagyon is létezik. Ha egy egyszerű gráfban nincsen kör akkor fa tehát van legalább két elsőfokú csúcsa és a)-ban csak egy van tehát van benne kör. Milyen hosszú lehet? Egy kör legalább 3 hosszú és egy 5 hosszú körnél minden pont fokszáma 2 lenne. Ha 3 hosszú akkor a többi él valahol csatlakozik a háromszöghöz, tehát a körön lévő egyik pont lesz 3 fokú, a másik kettő 2 fokú, tehát a 3-asból (legyen A) nem a háromszögbe indul egy él, legyen ez D, innen megint csak nem tudunk a háromszög pontjaihoz csatlakozni tehát a DE létezik és ez az egyik válasz: egy háromszög csúcsából induló 2 hosszú út. Ha a kör négy hosszú akkor egyszerűen látható hogy az ötödik pontot összekötve egyik csúccsal is pont megfelelőt kapunk.