Çözüm (Selim BAHADIR): Öğrencileri köşe, arkadaşlıkları kenar kabul eden grafı ele alalım. Köşe sayısı üzerinden tümevarım yapalım. Köşe sayısı $n$ olsun.
$n=2$ için $u$ ve $v$ öğrencileri arkadaş olduğundan $uv$ altın listedir.
$2\leq n \leq k$ için önerme doğru olsun. $n=k+1$ için olan duruma bakalım. Arkadaş olan iki öğrenciyi alalım, bunlar $u$ ve $v$ olsun. Grafımız $G$ olsun. $x$ öğrencisinin arkadaşlarını $N(x)$ kümesi ile gösterelim. $H=G \setminus (N(u) \cup N(v))$ fark kümesine bakalım. (Şekil 1).
$H= \varnothing $ ise, $uv$ bir altın listedir. (Şekil 2)
$H \neq \varnothing $ ise,
1. Durum: $H$ de izole köşe (hiç kenar çıkmayan köşe) yoksa, $H$ deki köşe sayısı $ \leq k$ olur. Tümevarım varsayımından, $H$ de çift sayıda öğrenci içeren bir altın liste var. Bu, $h_1h_2 \dots h_m$ olsun ($m$ çift). Bu durumda $h_1h_2 \dots h_muv$, $G$ de $m+2$ öğrenciden oluşan bir altın listedir.
2. Durum: $H$ de izole köşe varsa, bir izole köşe $w$ olsun. $N(w) \subseteq N(u) \cup N(v) $ olur. (Şekil 3)
Lemma: $G$ de, $uv$ ile başlayan bir altın liste vardır.
İspat: Önce $u$, sonra da $v$ arkadaşlarını yazar ve yeni olarak $u$ yazılmış oldu. Tahtada ismi yazılı olmayan biri varsa, $x_1$ olsun. $x_1$ in arkadaşlarından biri $v_1$ olsun. $v_1$ i listeye ekleyelim. $v_1$ arkadaşlarını yazdıktan sonra herkes yazılıysa $uvv_1$ altın listedir. Herkes yazılmamışsa, ismi yazılı olmayan biri $x_2$ olsun. $x_2$ nin bir arkadaşı $v_2$ olsun. $v_2$ yi listeye ekleyelim. İşlem tıkandığında (herkesin ismi listeye yazıldığında) bir altın liste elde etmiş olacağız. $uvv_1\dots v_r$, $G$ de $r+2$ elemanlı bir altın listedir.
Lemma'ya $N(w) \subseteq N(u) \cup N(v) $ olduğundan $w\neq u$, $w \neq v$, $w \neq v_i$ dir. Böylece $wuv v_1 \dots v_r$, $G$ de $r+3$ elemanlı bir altın listedir. $r+2$ ile $r+3$ ten biri çifttir. İspat tamamlanmış olur.
Not: ''Tek sayıda öğrenci içeren altın liste vardır'' önermesi doğru değildir. Ters örnek: $K_4$ tam grafı.
