Matematyka.pl

A dokladnie:
Czy graf k-krytyczny moze miec policzlnie nieskonczona liczbe wierzcholkow.
Ja mysle, ze nie moze, ale nie mam pojecia jak to udowodnic.
Prosze o pomoc
Dzieki

masz tam fakt (Theorem 1.), z ktorego wynika, ze kazdy graf krytyczny jest skonczony.

Sorry, ale nie bardzo to jest dla mnie jasne, bo ta teoria mowi o tym ze G nie moze byc (k+1) - colourable, ale przeciez numer chromatyczny moze byc mniejszy od k.
Tzn subgraph moze byc k- colourable ale miec numer chromatyczny 2, a G moze miec numer chromatyczny 3 i wtedy jest krytyczny?

W twierdzeniu jest wszystko, jak nalezy i trudno o jasniejsze sformulowanie. Jesli bariere stanowi jezyk, to sluze tlumaczeniem:

Twierdzenie 1. Niech \(\displaystyle{ k}\) bedzie liczba naturalna dodatnia i niech graf \(\displaystyle{ G}\) ma te wlasnosc, ze kazdy jego skonczony podgraf jest \(\displaystyle{ k}\)-kolorowalny. Wowczas graf \(\displaystyle{ G}\) jest \(\displaystyle{ k}\)-kolorowalny.

Teza twojego zadania wynika z tego twierdzenia natychmiast. Jesli bowiem graf nieskonczony bylby \(\displaystyle{ k}\)-krytyczny, to kazdy jego podgraf, w tym kazdy jego podgraf skonczony bylby \(\displaystyle{ k-1}\)-kolorowalny i wobec twierdzenia graf \(\displaystyle{ G}\) rowniez, co przeczy jego \(\displaystyle{ k}\)-krytycznosci.

Dziekuje bardzo