GR.II.6.1

Megoldás: 6.1
Feltesszük, hogy a gráfban nincs háromszög és megnézzük, maximálisan hány éle lehet. A megoldást hasonlóan kezdjük, mint a K.II.12.17. feladat megoldásában (az egész megoldást érdemes összevetni az ottani megoldással!!): kiválasztjuk a gráf egy maximális fokú x pontját. E maximális fokszámot most is d-vel jelöljük és most is S-sel jelöljük x szomszédait. A gráfban nincs háromszög, tehát S-ben nem fut él. Jelöljük T-vel a többi - tehát x-szel össze nem kötött - pont halmazát, és legyen ennek egy tetszőleges pontja y. Töröljük ki az y-ból induló éleket és húzzuk be helyette az y-t S pontjaival összekötő d darab élet. A d maximalitása miatt legalább annyi élt húztunk be, ahányat elhagytunk, tehát a gráf élszáma nem csökkent. Másrészt könnyen látható, hogy nem keletkezett háromszög, hiszen új háromszög csak úgy keletkezhetne, hogy annak egyik pontja y, de az y-nal összekötött pontok között nem fut él.

Ezt az eljárást megismételhetjük S minden pontjára, s ekkor eljutunk egy olyan páros gráfhoz, amelynek két osztálya S és T∪{x}, s köztük minden él be van húzva, azaz teljes páros gráfról van szó. Eközben nem csökkent a gráf élszáma.

Ismert, hogy egy n pontú teljes páros gráfnak akkor van a legtöbb éle, ha páros n esetén a két osztályban azonos számú pont van, páratlan n esetén akkor, ha a két osztály pontszáma eggyel tér el. Első esetben n2 /4 éle van a gráfnak, a második esetben ( n2 -1)/4 éle van. Az eredeti gráfnak is legfeljebb ennyi éle van tehát.

A bizonyításból most is az adódik, hogy egyenlőség pontosan akkor van, ha olyan teljes páros gráfról van szó, amelynek két osztályában vagy megegyezik a pontok száma (az n=2k páros eset), vagy eggyel különbözik (az n=2k+1 páratlan eset).

Megjegyzés. Érdemes végiggondolni, hogy ez az úgynevezett ,,szimmetrizálási eljárás" lényegében ugyanazt ,,csinálja", mint a ,,Vegyük a legnagyobbat" fejezetben adott megoldás (l. a K.II.12.17. feladat megoldását). Ez kicsit ,,szemléletesebben" mutatja azt, ami ott is történik.