Matematyka.pl

Witam, mam problem z zadaniem:
Na płaszczyźnie narysowano linie proste, w taki sposób że żadne trzy nie przecinają się w tym samym miejscu (czyli w jednym punkcie maksymalnie przecinają się tylko 2 proste odcinki). Wykaż że powstały graf jest 3-kolorowalny.

Oczywiście każdy graf planarny jest 4-kolorowalny (z twierdzenie o czterech barwach).
Oczywiście każdy wierzchołek ma stopień :
4 (standardowe przecięcie 2 odcinków)
lub 3 (gdy koniec odcinka przecina inny odcinek)
lub 2 (gdy stykają się dwa końce odcinków)
lub 1 (koniec odcinka).

Nie potrafię dojść w jaki sposób wykazać że graf jest 3-kolorowalny, oczywiście nie jest 2- kolorowalny (np "trójkąt"), a napewno jest 4-kolorowalny jak wyżej wspomniałem.

Za wszelką udzieloną pomoc z góry serdecznie dziękuje.

Ponumerujmy nasze proste w następujący sposób: jako k-tą wybieramy taką, dla której wszystkie punkty, poza do tej pozy ponumerowanymi, leżą po jednej jej stronie. Zacznijmy kolorować w dowolny poprawny sposób punkty na ostatniej prostej.

Następnie bierzemy poprzednią prostą i kolorujemy jakkolwiek poprawnie dowolny skrajny wierzchołek na niej, a następnie kolorujemy poprawnie kolejne z nich. Widzimy, że każdy dotychczas niepokolorowany wierzchołek z tej prostej ma co najwyżej 2 sąsiadów w zbiorze już pokolorowanych wierzchołków, więc uda się nam pokolorować wszystkie punkty z tej prostej.

Powtarzając czynności z poprzedniego akapitu w stosunku do prostych o coraz niższych numerach w końcu pokolorujemy poprawnie wszystkie wierzchołki.

pawels pisze:Ponumerujmy nasze proste w następujący sposób: jako k-tą wybieramy taką, dla której wszystkie punkty, poza do tej pozy ponumerowanymi, leżą po jednej jej stronie.

Zdanie jest nieścisłe, bo najpierw twierdzisz, że numerujesz proste, a później, że punkty. Czy chodziło o: "jako \(\displaystyle{ k}\)-tą wybieramy taką, dla której wszystkie punkty, poza przecięciami do tej pory ponumerowanych prostych, leżą po jednej jej stronie"?

Powinieneś jeszcze wyjaśnić, dlaczego tak się da. Przynajmniej pokaż to na przykładzie grafu, którego krawędzie są zawarte w przekątnych pięciokąta wypukłego.

\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){\circle*{4}}
\put(60,0){\circle*{4}}
\put(60,60){\circle*{4}}
\put(30,60){\circle*{4}}
\put(0,30){\circle*{4}}
\put(-8,-10){$1$}
\put(62,-10){$5$}
\put(62,62){$4$}
\put(23,62){$3$}
\put(-7,32){$2$}
\put(20,20){\circle*{4}}
\put(40,40){\circle*{4}}
\put(12,24){\circle*{4}}
\put(20,40){\circle*{4}}
\put(36,48){\circle*{4}}
\put(18,10){$8$}
\put(43,35){$7$}
\put(2,17){$9$}
\put(8,42){$10$}
\put(35,52){$6$}
\put(0,0){\line(1,1){60}}
\put(0,0){\line(1,2){30}}
\put(60,0){\line(-1,2){30}}
\put(60,0){\line(-2,1){60}}
\put(0,30){\line(2,1){60}}
\end{picture}}\)
Od której prostej należy zacząć?