Artykuł źródłowy w wersji do druku [application/pdf]: (66 KB)
Każdy punkt płaszczyzny pomalowano na czerwono, żółto lub niebiesko. Wykaż, że istnieją dwa punkty odległe o 1 i tego samego koloru.
Rozwiązanie
Rys. 1.Graf Golomba: 10 wierzchołków, wszystkie krawędzie długości 1.
Rys. 1.Graf Golomba: 10 wierzchołków, wszystkie krawędzie długości 1.
Rys. 2.Wrzeciono Mosera: 7 wierzchołków, wszystkie krawędzie długości 1.
Rys. 2.Wrzeciono Mosera: 7 wierzchołków, wszystkie krawędzie długości 1.
Nie da się pomalować wierzchołków grafu z rysunku obok trzema kolorami bez krawędzi o końcach jednego koloru. Jeśli bowiem środkowy punkt jest czerwony, to wierzchołki sześciokąta muszą być na przemian żółte i niebieskie. Jeśli punkty połączone z wewnętrznym trójkątem są niebieskie, to jego wierzchołki mogą być tylko czerwone i żółte, a to jak już wiemy daje tezę.
Zamiast grafu Golomba można w dowodzie użyć grafu z rysunku 2 lub lub z Delty 2/2013.
