Przypadek 1: lub Bez zmniejszenia ogólności, niech Tworzymy graf usuwając wierzchołek i tworząc kopię wierzchołka z takim samym jak zbiorem sąsiadów (nazwijmy ją ). Ponieważ nie ma krawędzi między i to żadna klika w nie zawiera obu wierzchołków. Stąd jeżeli nie zawierał kliki to również jej nie zawiera. Jednocześnie zawiera więcej krawędzi:
Przypadek 2: oraz W tym przypadku tworząc usuwamy wierzchołki oraz i tworzymy dwie kopie wierzchołka i Ponownie, ponieważ nie ma krawędzi pomiędzy i to w nie stworzymy kliki większej niż taka, która istniałaby już w Zauważmy jednak, że i w tym przypadku ma więcej krawędzi:
Teza 1 jest więc prawdziwa.
Zdefiniujmy relację Jest to relacja równoważności – jest w oczywisty sposób zwrotna i symetryczna, natomiast przechodniość wynika z udowodnionej właśnie tezy 1, ponieważ jeżeli w nie ma krawędzi między i oraz między i to nie może być też krawędzi między i Stąd wynika, że jest, dla pewnego pełnym grafem k-dzielnym, w którym podział wierzchołków odpowiada podziałowi na klasy abstrakcji relacji
Zauważmy, że musi być ponieważ w przeciwnym wypadku zawierałby jako podgraf klikę oraz że w pełnym grafie -dzielnym liczba krawędzi rośnie wraz z Stąd i z założenia, że ma maksymalną liczbę krawędzi, wynika ostatecznie, że i jest pełnym grafem -dzielnym.