Gráfelmélet (? )

Úgy tűnik, ha a legkisebb fokszámú csúcs fokszáma nem 0, akkor az egyi élét mindíg át lehet helyezni a gráfban máshova, ezzel az adott csúcs fokszámat csökkenteni úgy, hogy az összes élek száma megmaradjon.

Akkor viszont tényleg (k-1 alatt 2) lesz a maximum.

Szerintem is (k-1 alatt 2). Magyarul egy maximális ismertség előáll úgy, ha van egy ember, akit senki sem ismer, a maradék k-1 ember viszont mind ismeri egymást.

BKRS bizonyítása nagyon szép, az enyém nyögvenyelősebb :) Én a szomszédossági mátrix-ba gondoltam bele. 1 van a mátrix [u,v] pozíciójában, ha u és v ismeri egymást. (Persze [v,u]-ban is 1 van ilyenkor. A főátlóban pedig nullák vannak.) A mátrixban az 1-esek száma összegének a fele az ismertségek (élek) száma.

Ha két ember (u és v) ismeri egymást, akkor kell legalább egy olyan sornak (w) lennie a mátrixban, ahol az u és a v oszlopban is 0 van. Vagyis az [u,w] és [v,w] pozícióknak is 0 az értéke. Ez a w az az ember, akit egyikük sem ismer. (Persze a [w,u] és [w,v] pozíciókban is nulla van, de ezeket nem is írom többet.)

Ha x és y is ismeri egymást, akkor őhozzájuk is kell egy olyan z sornak lennie, ahol mindkét oszlopban 0 van.

Ha van n ember (oszlop), akik között vannak ismertségek (nem feltétlenül mindenki mindenkivel, de persze az lenne az optimális), akkor ebben az n oszlopban kell lennie legalább oszloponként egy 0-nak. Vagyis van legalább n darab 0.

Akkor van a legkevesebb 0, ha minden nulla egyetlen sorban van. Ellenkező esetben, ha mondjuk az előző u,v-hez az [u,w] és [v,w] nullák tartoznak, x,y-hoz pedig [x,z] és [y,z], akkor ha mondjuk u és x is ismeri egymást, akkor legalább még egy nullának kell lennie (mondjuk az [u,z] pozíción). Vagyis így oszloponként egynél több nulla is lenne. Tehát (k-1 alatt 2)-nél csak kevesebb hely maradna az 1-esek számára.

---

Ez a bizonyítás mondjuk azt is megmutatja, hogy (k-1 alatt 2)-őt csak a triviális módon lehet elérni; ez BKRS bizonyításából nem jön ki. Ennek ellenére az szebb :)