Lemat w związku z grafami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

Lemat w związku z grafami

Post autor: matinf »

Witam,
Mam takie coś.

Powiedzmy, że mamy pokolorowany graf (zgodnie z typowoą zasadą - dwa węzły o tym samym kolorze nie mogą być incydentne).
Pokazać, że wówczas wybierając dowolny kolor (powiedzmy czerwony) zawsze wśród czerwonych istnieje jakiś węzeł który jest połączony ze wszystkimi kolorami.


Nie wprost chyba tylko.
Jeśli założymy nie wprost to, żaden z czerwonych węzłów nie ma połączenia ze wszystkimi kolorami. Tzn każdemu brakuje choć jednego z kolorów - powiedzmy: jednemu niebieskiego, innemu zielonego..

Ok i ja teraz mówię tak:
Popatrzmy na wszystkie czerwone. Każdemu z nich czegoś brakuje (zakładamy nie wprost). No więc ten czerwony węzeł zamieniamy na ten kolor z którym on nie ma połączenia. (przemalowanie). Jest możliwe, bo nie psujemy nic - i tak i tak nie było połączenia - brak konfliktu. Czyli udało się zredukować liczbę kolorów. A to sprzeczne ! Bo ten graf nie był pokolorowany "prawidłowo", tzn najmniejszą liczbą kolorów. Czyli twierdzenie jest prawdziwe.


Czy ten dowód jest Ok ?
ODPOWIEDZ