Matematyka.pl

Udowodnić, że w \(\displaystyle{ K_6}\) dowolnie pokolorowanym krawędziowo na 2 kolory jest trójkąt monochromatyczny, ale w \(\displaystyle{ K_5}\) już nie.

Jak mozna to rozwiązać ?

Przypadek \(\displaystyle{ K_6}\).

Ustal jeden wierzchołek grafu. Z zasady szufladkowej Dirichleta wynika, że istnieją trzy krawędzie jednego koloru (powiedzmy czerwone) wychodzące z tego wierzchołka. Spróbuj teraz kolorować krawędzie łączące wierzchołki, które połączyłeś czerwonymi krawędziami ze startowym wierzchołkiem.

Przypadek \(\displaystyle{ K_5}\).

Istnieje kolorowanie zawierające trójkąt monochromatyczny. Zapewne chodzi więc o wskazanie kolorowania bez takiego trójkąta. No to jest wyłącznie metoda prób i błędów.

Ok, no faktycznie widzę, że "musi" wyjść jeden trójkąt, ale nie wiem jak powinienem to sformalizować. Napiszę najlepiej jak potrafię, sam ocenisz.




No widać, że żółta linia na koniec symbolizuje, że to koniec - ona musi być czerwona, niebieska - tak czy inaczej zamknie trójkąt. A 2gi etap został wykonany w sposób "przymuszony" Gdyby te linie były inne, to wówczas zamykamy od razy trójkąt chromatyczny.

Jednak to jeszcze nie jest dowód przecież. 1szy etap (wybór 3 krawędzi nie jest Ok)
Chodzi o to, że 3 krawędzie będą na prawdę tego samego koloru (co najmniej 3), ale ja byłem trochę tendecyjny przy wyborze.
Co powiesz o tym 1szym etapie ? On nie był zupełnie dowolny - tzn wybrałem 3 do kolorwania na jeden kolor - ale wybrałem 3 szczególne w jakiś sposób.

matinf pisze: No widać, że żółta linia na koniec symbolizuje, że to koniec - ona musi być czerwona, niebieska - tak czy inaczej zamknie trójkąt. A 2gi etap został wykonany w sposób "przymuszony" Gdyby te linie były inne, to wówczas zamykamy od razy trójkąt chromatyczny.

I o to właśnie chodziło w tej części. Przez rozpatrzenie przypadków można łatwo dojść do jednokolorowego trójkąta.

matinf pisze: Jednak to jeszcze nie jest dowód przecież. 1szy etap (wybór 3 krawędzi nie jest Ok)
Chodzi o to, że 3 krawędzie będą na prawdę tego samego koloru (co najmniej 3), ale ja byłem trochę tendecyjny przy wyborze.
Co powiesz o tym 1szym etapie ? On nie był zupełnie dowolny - tzn wybrałem 3 do kolorwania na jeden kolor - ale wybrałem 3 szczególne w jakiś sposób.

No to wybierz jakiekolwiek trzy inne i powtórz rozumowanie i rysunki z tego szczególnego, opisanego wyżej. Dostaniesz analogiczne obrazki i wyciągniesz analogiczne wnioski.

Jeżeli chcesz to zrobić formalnie, to możesz ustalić wierzchołek \(\displaystyle{ v}\) i dobrać wierzchołki \(\displaystyle{ a, b, c}\) a następnie wziąć czerwone krawędzie niezorientowane \(\displaystyle{ (v,a), (v,b), (v,c)}\). Z zasady szufladkowej wiemy, że mamy takie trzy krawędzie, które mają etykiety czerwone i je właśnie wybraliśmy. Aby nie dostać trójkąta jednokolorowego, jaką etykietę przypiszesz krawędziom \(\displaystyle{ (a,b)}\) oraz \(\displaystyle{ (c,b)}\)? Co wtedy z krawędzią \(\displaystyle{ (a,c)}\)? Czy zmiana wyboru pary krawędzi wpływa na dalsze rozwiązanie?

yorgin pisze:No to jest wyłącznie metoda prób i błędów.

Oprócz metody prób i błędów są jeszcze co najmniej dwie:
1. Przyjrzeć się dowodowi dla sześciu wierzchołków. Wywnioskować, że w kontrprzykładzie dla pięciu z każdego wierzchołka muszą wychodzić po dwie krawędzie każdego koloru.
2. Przypadkiem natknąć się na rysunek pięciokąta, w którym boki są jednego koloru, a przekątne innego.