Gyenizse Gergő megoldása. (1) Tekintsük a barátsági kapcsolatokat megjelenítő $G$ gráf pontjainak egy olyan felosztását egymástól diszjunkt $A$ és $B$ halmazokra, amelyre az $A$-ban található maximális méretű klikk legalább akkora, mint a $B$-ben található, és a két méret különbsége a lehető legkisebb. Ha e különbség pozitív, akkor megmutatjuk, hogy az értéke 1. Ellenkező esetben az $A$ pontjait egyesével rakjuk át $B$-be; egy pont áthelyezésével az $A$-beli maximális méretű klikk mérete legfeljebb 1-gyel csökken, a $B$-belié legfeljebb 1-gyel nő, így a különbség legfeljebb 2-vel csökken.
(2) Ha a feladat állítása hamis, akkor tehát az $A$-beli maximális méretű klikk mérete $a$, a $B$-belié pedig $a-1$. A $G$-ben nincs $2a$-klikk, hiszen akkor abból vagy $A$-ba esne $\left(a+1\right)$-klikk, vagy $B$-be egy $a$-klikk. A feladat feltétele szerint ekkor viszont $\left(2a-1\right)$-klikk sem létezhet $G$-ben.
(3) Ha $A$-nak valamely $x$ pontja nem tartozik hozzá egy $A$-beli $a$-klikkhez, akkor nincs olyan $B$-be eső $\left(a-1\right)$-klikk, amelynek minden pontja össze van kötve $x$-szel: ellenkező esetben ugyanis ezt az $x$ pontot $B$-be áthelyezve az $A$-beli maximális klikkméret továbbra is $a$, a $B$-belié pedig szintén $a$-ra nőne.
(4) Megmutatjuk, hogy $A$-ban csupán egyetlen $a$-klikk található. Tegyük fel ugyanis, hogy van kettő; az egyiket jelölje $C$, és tegyük át $A$-nak a $C$-hez nem tartozó pontjait egyesével $B$-be. Ennek során $B$-ben ((3) szerint) nem keletkezhet $\left(a-1\right)$-nél nagyobb méretű klikk. Legyen $p$ az a pontja $A$-nak, amelynek átrakása előtt még két $a$-klikk is található $A$-ban, utána viszont már csak egy, $C$. Jelölje továbbá $q$ a $C$-nek egy olyan pontját, amely nincs összekötve $p$-vel. (Biztosan van ilyen pont, különben $p$ a $C$-vel $\left(a+1\right)$-klikket alkotna.) Tegyük vissza a $p$ után áthelyezett pontokat $A$-ba, a $q$ pontot pedig rakjuk $B$-be. Azt állítjuk, hogy ekkor viszont $A$-ban és $B$-ben egyaránt $a-1$ a maximális klikkméret (ami ellentmondás). Valóban, $q$-val együtt csak $C$ volt $a$-klikk az $A$-ban, ami $q$ eltávolításával megszűnik. A (3) szerint $q$ átkerülése előtt $B$-ben nem keletkezhet $a$-klikk, tehát csak úgy jöhetne végül létre, hogy $q$ össze van kötve egy eredetileg is $B$-be tartozó $\left(a-1\right)$-klikk valamennyi pontjával. Ekkor viszont a következőképpen módosíthatunk: az eredeti $A$-ból csupán $q$ kerüljön át $B$-be, ezzel ott létrejön egy $a$-klikk; $A$-ban viszont megmarad az a $C$-től különböző $a$-klikk, amely korábban $p$ áttételével szűnt csak meg, ezért szükségképpen tartalmazza $p$-t. Így azonban nem tartalmazza $q$-t, hiszen $p$ és $q$ nincs összekötve. Ebben az elrendezésben tehát $A$ és $B$ maximális klikkmérete egyaránt $a$, ami ellentmondás.
(5) Jelölje a (4) szerint egyetlen $A$-beli $a$-klikket $C$, és helyezzük át az $A$ összes, $C$-n kívüli pontját $B$-be; ennek során $B$ maximális klikkmérete változatlanul $a-1$ marad. Ha viszont ezután $C=A$ bármelyik $y$ pontját $B$-be helyezzük, akkor $A$ maximális klikkmérete $\left(a-1\right)$-re csökken, ezért ‐ eredeti indirekt feltevésünk értelmében ‐ $B$-ben $a$-klikk jön létre, méghozzá (4) szerint pontosan egy, jelöljük $D$-vel. A $D$-nek létezik olyan $z$ pontja, ami az $A$-ból megmaradt $\left(a-1\right)$-klikk valamelyik pontjával nincs összekötve, hiszen ellenkező esetben a két halmaz $\left(2a-1\right)$-klikket alkotna $G$-ben, ellentmondva (2)-nek. Így azonban a $z$ pontot az $A$-ba téve, ott továbbra is $a-1$ marad a maximális klikkméret, $B$-ben pedig $\left(a-1\right)$-re csökken, mivel $D$, az egyetlen $a$-klikk a $z$ eltávolításával megszűnik. Ez ellentmond eredeti indirekt feltevésünknek.