Punkty i kolory

[mol_ksiazkowy]

W przestrzeni danych jest \(\displaystyle{ n \geq 4}\) takich punktów, że żadne cztery spośród nich nie leżą na wspólnej płaszczyźnie. Każde dwa z tych punktów są połączone odcinkiem białym lub czarnym. Udowodnić, że istnieje taki kolor, że każde dwa z tych punktów są połączone odcinkiem bądź też łamaną tego koloru.

[Dakurels]

Rozważmy graf, w którym każdy wierzchołek odpowiada jednemu z punktów w przestrzeni, a krawędzie odpowiadają czarnym odcinkom (odpowiednio dopełnienie grafu, będzie grafem, w którym krawędzie odpowiadają białym odcinkom). Taki kolor będzie istnieć wtedy i tylko wtedy, gdy ten graf, lub jego dopełnienie będą posiadać drzewo rozpinające. Jeśli graf jest spójny, to posiada drzewo rozpinające i wtedy tym kolorem jest kolor czarny. Natomiast jeśli graf nie jest spójny, wtedy weźmy dwie dowolne spójne składowe. Niech wierzchołek v, należy do pierwszej spójnej składowej, a wierzchołek u, do drugiej spójnej składowej. Łatwo widać, że wierzchołek v, będzie posiadał, w dopełnieniu grafu, krawędzie do wszystkich wierzchołków nienależących do jego spójnej składowej (w szczególności do u), natomiast u, będzie posiadać krawędzie do wszystkich wierzchołków z pierwszej spójnej składowe, co czyni dopełnienie grafu spójnym, ponieważ z wierzchołka v, można dostać się jedną krawędzią do każdego wierzchołka, nie należącego do jego spójnej składowej, natomiast dwoma krawędziami, przechodząc przez wierzchołek u, można dostać się do wierzchołków z jego spójnej składowej (co jest wymaganym drzewem rozpinającym).