Matematyka.pl

Przerabiamy punkty na wierzchołki a odcinki na krawędzie - robimy graf. Każdy wierzchołek ma stopień co najwyżej \(\displaystyle{ 11}\). Korzystając z metody z powyższego zadania możemy tak podzielić wierzchołki na dwie grupy \(\displaystyle{ A}\) i \(\displaystyle{ B}\), że każdy będzie miał co najwyżej \(\displaystyle{ 5}\) sąsiadów w swojej grupie. Tam co prawda jest warunek, że każdy ma co najmniej \(\displaystyle{ n}\) sąsiadów, a tutaj jest na odwrót, ale to nic nie zmienia - robimy następujące operacje: jeżeli wierzchołek ma więcej niż \(\displaystyle{ 5}\) sąsiadów w swojej grupie to przerzucamy go do drugiej grupy, zmniejsza to łączną liczbę krawędzi znajdujących się wewnątrz zbiorów. Nie możemy wykonywać takich operacji w nieskończoność (z zasady minimum), więc w pewnym momencie nie będzie już istniał wierzchołek mający więcej niż \(\displaystyle{ 5}\) sąsiadów w swoim zbiorze.
Teraz postępujemy analogicznie wewnątrz każdej z tych dwóch grup - dostaniemy podział na \(\displaystyle{ 4}\) grupy. Weźmy grupę A. Możemy podzielić wierzchołki z tej grupy na dwie grupy \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) tak, że każdy w swojej grupie będzie miał co najwyżej \(\displaystyle{ 2}\) znajomych. Analogicznie w grupie \(\displaystyle{ B}\) dostajemy grupy \(\displaystyle{ P}\) i \(\displaystyle{ Q}\). W każdej z grup \(\displaystyle{ X}\), \(\displaystyle{ Y}\), \(\displaystyle{ P}\) i \(\displaystyle{ Q}\) każdy wierzchołek jest połączony z co najwyżej \(\displaystyle{ 2}\) w swojej grupie, a każda z tych grup zawiera co najwyżej \(\displaystyle{ n}\) wierzchołków, czyli suma stopni wierzchołków krawędzi wewnętrznych każdej z tych grup jest równa co najwyżej \(\displaystyle{ 2n}\), więc liczba krawędzi w każdej z tych grup jest równa co najwyżej \(\displaystyle{ n}\). Kolorujemy wierzchołki na \(\displaystyle{ 4}\) kolory tak jak podzieliliśmy je na grupy.