Megoldás: 9.6
1. megoldás.
Ha
n=3, akkor lehet három éle, a háromszögben nincs két független él. Minden más
n értékre
n-1 a maximum, és ha
n nem 3 vagy 4, akkor egyetlen
n pontú,
n-1 élű egyszerű gráf van, amiben nincs két független él: az
n pontú csillag.
Tegyük fel, hogy a
G gráfban nincs két független él, és legyen
xy a gráf egy éle. Minden további
e él egyik végpontja
x, vagy
y, ellenkező esetben
e független volna
xy-tól. Ha van olyan
z pont, amellyel
x is,
y is össze van kötve, akkor a gráfban nem lehet további él, hiszen az e három él valamelyikétől független lenne. Ha pedig nincs ilyen
z pont, akkor vagy
x-ből, vagy
y-ból nem indul él, hiszen ha volna egy
xu és egy
yv él, ezek függetlenek volnának (
u≠v). Tehát a gráf minden éle
x-ből indul (vagy minden éle
y-ból indul). Nyilvánvalóan akkor van a legtöbb él, ha a gráf egy csillag.
A kritikus gráf tehát az
n pontú csillag és az a gráf, amely egy háromszögből és
n-3 darab izolált pontból áll.
Ebből már következik, hogy
n=3-ra a maximális élszám három, a háromszög a maximális élszámú gráf, ha viszont
n≥4, akkor a maximális élszám
n-1.
n=4-re a hárompontú csillag is, a háromszögből és egy izolált pontból álló gráf is maximális élszámú, ha
n>4, akkor csak az
n pontú csillagnak van maximális élszáma.
2. megoldás.
Lényegében ugyanez a bizonyítás elmondható az
1.15. feladatra hivatkozva is. Nevezzük
kritikus gráfnak azokat az egyszerű gráfokat, amelyekben nincs két független él, de bármely még nem szereplő élt behúzva már keletkezik két független él. Az említett feladat szerint egy ilyen gráfban vagy van telített pont, vagy van izolált pont. De az izolált pontokat nyugodtan elhagyhatjuk, ettől a gráf továbbra is kritikus gráf marad és most már biztosan van benne telített pont, legyen ez
x. Ha
x két szomszédja között fut egy
e=yz él, akkor
x-nek nem lehet további szomszédja. Ha ugyanis
u egy további szomszédja volna, akkor
xu és
yz két független él volna. Tehát az izolált pont nélküli kritikus gráfok a háromszög és a csillag.