Dowód: graf + liczba chromatyczna

[matinf]

Witam,

\(\displaystyle{ n}\) to dodatnia liczba naturalna.
Pokazać, że \(\displaystyle{ (x-n)}\) jest czynnikiem wielomianu \(\displaystyle{ P_G(x)}\) wtw gdy \(\displaystyle{ n < K(G)}\)
Za \(\displaystyle{ K}\) uważam liczbę chromatyczną. Zaś za literę P wielomian chromatyczny.

Chciałbym prosić o wsparcie przy tym dowodzie.

Spróbuję najpierw powiedzieć co w ogóle rozumiem z tego twierdzenia.

Najpierw z lewa na prawą.

Wiadomo więc, że \(\displaystyle{ (x-n)}\) jest czynnikiem wielomianu chromatycznego. Oznacza to, że co najmniej jeden z wierzchołków ma stopień choćby n. Dlatego, że decydując się malować jeden z węzłów mamy do wyboru \(\displaystyle{ x-n}\) kolorów, a więc któryś z węzłów ma taki stopień (co najmniej taki). No nie wiem czy to dobre rozumowanie...

[bartek118]

Jak \(\displaystyle{ (x-n)}\) jest składnikiem tego wielomianu to znaczy, że nie istnieje kolorowanie przy użyciu \(\displaystyle{ n}\) kolorów i de facto to tyle.

[matinf]

Tak, to jest prawda. Okazuje się, że za pomocą n kolorów można pomalować na 0 sposobów.

Ale dlaczego od razu to oznacza, że liczba chromatyczna musi być większa ?

[norwimaj]

Bo jak nie możesz pokolorować \(\displaystyle{ n}\) kolorami, to tym bardziej nie pokolorujesz \(\displaystyle{ k}\) kolorami dla \(\displaystyle{ k<n}\). Każde \(\displaystyle{ k}\)-kolorowanie jest też \(\displaystyle{ n}\)-kolorowaniem.

[matinf]

Tak, to jest prawda rzeczywiście. Więc ja sformalizuję:

z lewej na prawą:

Załóżmy, że \(\displaystyle{ (x-n)}\) jest czynnikiem. Wówczas dla tej liczby kolorów (n) mamy zero sposobów kolorowania grafu. A więc jasne jest, że żadna liczba mniejsza też nie starczy, stąd liczba chromatyczna musi być większa

W drugą stronę równie łatwo.

Załóżmy, że liczba chromatyczna jest większa. A więc nie można pokolorować na mniejszą ilość kolorów, tzn że jest zero sposobów, a więc wielomian chromatyczny musi się zerować dla tej wartości. Tak więc ten czynnik na prawdę istnieje.