Teza 2: Liczba krawędzi w pełnym grafie -dzielnym jest maksymalna, kiedy wielkości części podziału zbioru wierzchołków różnią się co najwyżej o 1.
Niech będzie pełnym grafem -dzielnym, w którym istnieją części podziału i takie, że Możemy zwiększyć liczbę krawędzi w przenosząc wierzchołek ze zbioru do zbioru Wskutek przeniesienia usuniemy z grafu krawędzi, jednocześnie dodając krawędzi. W ostatecznym rozrachunku dodajemy krawędzi, co dowodzi tezy 2.
Z powyższego dowodu wynika, że spośród grafów -wierzchołkowych niezawierających kliki najwięcej krawędzi ma graf Turána
Zobacz też graf Turána
Turána