Teoria grafów

[flake]

1. Uzasadnij, ze gdy krawedzie grafu K17 pokolorujemy trzema kolorami, to znajdzie sie
przynajmniej jeden trójkat jednego koloru.

2. Krawedzie grafu K5 kolorujemy dwoma kolorami. Wykaz, ze przynajmniej piec ma ten
sam kolor. Czy zawsze istnieje trójkat jednego koloru?

[*Kasia]

W pierwszym, zacznij od zauważenia, że z jednego wierzchołka wychodzi co najmniej sześć krawędzi jednego koloru i zadanie sprowadza się do wykazania, że w sześciokącie istnieje trójkąt jednego koloru. Dowodzimy podobnie: z jednego wychodzą co najmniej trzy odcinki w jednym kolorze. I albo wśród odcinków łączących ich końce jest jakiś w tym samym kolorze, albo wszystkie są w innym i tworzą trójkąt.

W drugim: jest 10 krawędzi. Z zasady szufladkowej wynika, że co najmniej pięć jest w tym samym kolorze.
Nie musi istnieć, poszukaj przykładu.