Az I/30. feladat megoldása:
Tegyük fel, hogy nem. Ekkor van egy V1 versenyző, aki legfeljebb 15 másikkal játszott, különben az összes versenyző halmaza megfelel. Legyen az összes versenyző halmaza H és tekintsük a H1=H–V1 halmazt. Ha ez nem megfelelő, akkor van egy olyan V2 versenyző benne, aki a H1 tagjai közül legfeljebb 15-tel mérkőzött. Tegyük fel, hogy a V1, V2, …, Vk versenyzőkrol már tudjuk, hogy közülük Vi a H–{V1,V2,…,Vi–1} halmazba tartozó versenyzők közül legfeljebb 15-tel játszott.
Tekintsük a H–{V1,V2,…,Vk} halmazt. Ha ez sem megfelelő, akkor itt is van egy Vk+1 versenyző, aki a halmazban szereplő többi versenyző közül legfeljebb 15-tel játszott. Így végül azt kapjuk, hogy a versenyzők sorozatba rendezhetők úgy, hogy mindenki legfeljebb 15-tel játszott azok közül, akik a sorozatban később következnek. Az utolsó 15 emberről ráaadásul az is nyilvánvaló, hogy kevesebb, mint 15-tel játszottak, hiszen utánuk már csak kevesebb, mint 15-en vannak. De ez azt jelenti, hogy az összes lejátszott mérkőzés száma kevesebb, mint 15n, hol n az összes versenyző száma. Ezesetben viszont a versenyzők átlagosan kevesebb mint 30 mérkőzést játszhattak (lásd a 12. feladatot).A pontos állítás tehát a következo:Ha egy gráfban az átlag fokszám legalább 2k, akkor van olyan feszített részgráfja, amelyben minden pont foka legalább k+1.