Matematyka.pl

zad. 1

Pokazać, że jeżeli każda krawędź grafu \(\displaystyle{ K _{(r-1) ^{2}+1 }}\) jest pokolorowana na czerwono lub zielono, to albo każde drzewo na r wierzchołkach jest czerwone, albo każde drzewo na r wierzchołkach jest zielone.

zad. 2

Które z podanych grafów są izomorficzne?

grafy izomorficzne mają identyczne stopnie wierzchołków i identyczne połączenia krawędzi z wierzchołkami - teraz wystarczy po prostu przeanalizować dokładnie wszystkie rysunki
wtedy dochodzimy do wniosku, że izomorficzne są grafy:
1, 2 i 7 oraz 5 i 6 (ale lepiej upewnić się samemu, bo człowiek jest z natury omylny)

ma ktos moze jakas wskazowke jak pierwsze ruszyc?

Odnośnie zadania 1:
Rozważmy graf \(\displaystyle{ K_5}\) z krawędziami pokolorowanymi na zielono i czerwono tak, aby istniała krawędź w kolorze czerwonym i krawędź w kolorze zielonym. Wtedy istnieje wierzchołek \(\displaystyle{ v}\) taki, z którego wychodzi krawędź czerwona i zielona. Niech \(\displaystyle{ vu}\) będzie krawędzią czerwoną, a \(\displaystyle{ vw}\) krawędzią zieloną. Wtedy drzewo rozpięte na wierzchołkach \(\displaystyle{ u,v,w}\) z krawędziami \(\displaystyle{ uv,vw}\) nie jest monochromatyczne.

Nie powinno być przypadkiem, że w grafie \(\displaystyle{ K_{(r-1)^2 + 1}}\) istnieje monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach?

[edit]W tym drugim przypadku dowód nie jest trudny. Każdy wierzchołek w \(\displaystyle{ K_{(r-1)^2 + 1}}\) ma \(\displaystyle{ (r-1)^2}\) sąsiadów. Z zasady szufladkowej wynika, że istnieje wierzchołek, z którego wychodzi co najmniej \(\displaystyle{ \frac{(r-1)^2}{2}}\) krawędzi w kolorze czerwonym. Te krawędzi dadzą ci monochromatyczne drzewo na \(\displaystyle{ r}\) wierzchołkach, jeśli \(\displaystyle{ \frac{(r-1)^2}{2} q r-1}\).