Létezik-e olyan társaság ahol az ismerettségek száma (9,9,9,8,8,8,7,6,4,4)?

Ha az ismertség azt jelenti, hogy kölcsönösen ismerik egymást, akkor nem létezik.

Ugyanis egy olyan egyszerű gráfot kellene csinálni, amiben a csúcsok fokszáma az adott szám.

A szükséges feltétel, vagyis hogy a fokszámok összege páros, az teljesül, de ez nem elégséges.

Adott fokszámú csúcsokból álló egyszerű gráf akkor készíthető, ha a Havel-Hakimi algoritmus le tud futni a fokszámokon:

9 9 9 8 8 8 7 6 4 4

A legnagyobb fokszámú csúcsot kötjük a 9 következőhöz, majd kidobjuk, a kötöttek fokszáma is csökken 1-gyel:

- 8 8 7 7 7 6 5 3 3

Ezt ismételjük többször:

- - 7 6 6 6 5 4 2 2

- - - 5 5 5 4 3 1 1

- - - - 4 4 3 2 0 1 (csak 5-öt kellett csökkenteni, újrarendezzük csökkenő sorrendbe)

- - - - 4 4 3 2 1 0 (ez a rendezett, most dolgozzuk fel a 4-et)

- - - - - 3 2 1 0 0

- - - - - - 1 0 -1 0 !!!! negatív lett, nem jó, nincs ilyen gráf.

Megjegyzés:

Ez az algoritmus egyébként, ha lefut, akkor a lehetséges gráfok közül egyet készít el, de lehetnek más gráfok is.

Annak bizonyítása, hogy ha létezik egy keresett fokszámú gráf, akkor létezik olyan is, amit ez az algoritmus készítene, (magyarul, hogy ez az algoritmus elégséges feltételt ad arra, hogy adott fokszámú csúcsokból álló gráf létezik,) az mondjuk ilyesmi lehet:

Tegyük fel, hogy A, B, C a gráf 3 csúcsa (a sok közül), fokszámaik a,b,c ahol a ≥ b ≥ c, és van él az A csúcsból a C-be, de nincs a B-be. (Ez a gráf különbözne attól, amit a Havel-Hakimi csinál.) Mivel van C-be él, ezért c legalább 1, és b ≥ c miatt b is legalább 1. Tehát van él B-ből valahová, nevezzük ezt X-nek, ahol X ≠ C. Vagyis van egy AC és egy BX él is. Ha ezeket az AC és BX éleket az AB és CX élekkel helyettesítjük, a fokszámok nem változnak, és Havel-Hakimi stílusúvá válik a gráf (elegendő ilyen módosítás után).

(Az X≠C feltétel nem azt jelenti, hogy ne lehetne BC él, viszont ha van olyan, akkor b ≥ c ≥ 2, tehát kell lennie B-ből egy másik élnek is, az lesz az X.)