„Matematyk
to przyrząd do przerabiania kawy na twierdzenia matematyczne”
Alfred Rényi
Już po tym cytacie widać, że mamy do czynienia z
kimś wyjątkowym. A był
nim Paul Erdös jeden z największych, najbardziej płodnych i
najoryginalniejszych matematyków wszechczasów. Sypiał w nocy tylko trzy godziny,
matematyką zaś zajmował się po 19 godzin dziennie, siedem dni w tygodniu, aż do
dnia śmierci w wieku 83 lat. Uważał, że matematyk to przyrząd do przerabiania
kawy na twierdzenia matematyczne.
Paul Erdös urodził się 26 marca 1913 roku w
Budapeszcie. W kilka dni po jego urodzeniu obie jego siostry (w wieku trzech i
pięciu lat) zmarły na szkarlatynę. Rodzice Paula, nauczyciele matematyki, zawsze
uważali, że dziewczynki były o wiele bystrzejsze od niego. Kiedy Paul miał
półtora roku, jego ojciec został schwytany przez Rosjan podczas ataku na
Cesarstwo Austro-Węgierskie i na sześć lat zesłany na Sybir.
W 1917 roku, zanim skończył cztery lata, Erdös
umiał już mnożyć w pamięci liczby czterocyfrowe. Musiał liczyć w pamięci, bo nie
umiał jeszcze tych liczb zapisać. Jednakże jego głównym osiągnięciem w tym
czasie było samodzielne odkrycie liczb ujemnych. Pewnego razu powiedział do
swojej mamy: „Jeśli odejmiesz 250 od 100, to dostaniesz 150 poniżej zera".
Do szkoły poszedł, gdy był już nastolatkiem,
ponieważ wcześniej matka uczyła go sama w domu. Obawiała się, że w szkole złapie
jakąś infekcję i umrze jak jego siostry.
Paul
Erdös w dzieciństwie
Mając 17 lat Erdös poszedł na uniwersytet, a
kiedy miał ok. 19 lat, napisał swoją pierwszą pracę i udowodnił pierwsze
twierdzenie. Mówiło ono, że zawsze znajdzie się co najmniej jedna liczba
pierwsza między liczbą n a 2n. Mówiąc prościej, zawsze można znaleźć chociaż
jedną liczbę pierwszą pomiędzy liczbami np. 3 i 6, 400 a 800 . Pierwszy dowiódł
tego twierdzenia Czebyszew, ale dowód Erdösa był „o wiele lepszy i
schludniejszy". Erdös stał się nagle sławny wśród europejskich matematyków. Dla
uczczenia jego sukcesu powstał nawet mały wierszyk:
„Powiedział to Czebyszew, ja zaś powiem
inaczej,
Zawsze między n a 2n liczbę pierwszą
zobaczę.”
Mając lat 21, otrzymał stopień doktora i od 1934
roku kontynuował matematyczną karierę na Uniwersytecie w Manchesterze. Pod koniec lat 30. XX wieku nagonka na Żydów
była tak wielka, że Erdös nie mógł wrócić na Węgry. Dlatego wyemigrował do
Stanów Zjednoczonych. Podczas II wojny światowej większość jego krewnych
mieszkająca na Węgrzech została zamordowana.
W czasach zimnej wojny osoba ekstrawertycznego
matematyka budziła w Stanach Zjednoczonych podejrzenia. Ubierał się bowiem
dziwacznie i miał silny europejski akcent. A w Stanach panicznie bano się
wówczas komunizmu. Pewnego razu, kiedy Erdös próbował powrócić do kraju z
jakiejś podróży, urzędnik na granicy zapytał go o Karola Marksa. Erdös nie
wiedział zbyt wiele na jego temat, więc odpowiedział szczerze: „Nie jestem
kompetentny, żeby go osądzać, ale niewątpliwie był to wielki człowiek". Przez to
jedno zdanie nie wpuszczono go do kraju.
Erdös miał mnóstwo najróżniejszych kłopotów z
władzami. Rosjanie nie lubili go za to, że spędzał tak dużo czasu w Stanach
Zjednoczonych. Brytyjczycy nie lubili go, bo korespondował z jednym z
matematyków w komunistycznych Chinach i w swoich listach używał wielu
matematycznych symboli. Uważano, że owe symbole to rodzaj jakiegoś sekretnego
kodu.
Większość dziesięciolecia lat 50. XX wieku Erdös
spędził w Izraelu, lecz w końcu na początku lat 60. pozwolono mu wrócić do
Stanów. Cały czas jednak wędrował po świecie, szukając problemów do rozwiązania.
Ciekawym epizodem w jego życiu była "afera zdjęciowa". Wraz z
Anglikiem Arthurem Stone'em i Japończykiem Shizuo Kakutani wdrapali się na
stojącą na wzniesieniu wieżę, z której szczytu chcieli obserwować morze i
rozmyślać o matematyce. W swym matematycznym zapale przeoczyli jednak tablicę
ostrzegawczą z napisem „Wstęp surowo wzbroniony”. Dodatkowo, zrobili tam kilka
pamiątkowych zdjęć. Po dostrzeżeniu ich na szczycie wieży zostali aresztowani
przez FBI i oskarżeni o szpiegostwo. Zarzut szpiegostwa nie został jednak
ostatecznie udowodniony i Paul Erdős został oczyszczony z zarzutów.
Arthur Stone
Shizuo Kakutani
Erdös kochał tylko matematykę
Nie troszczył się o własność osobistą, jedzenie,
ubrania ani o podatki. Nigdy nie nauczył się przygotowywać posiłków, potrafił
tylko dolać mleko do płatków śniadaniowych. Jego jedyną własność stanowiło kilka
starych ubrań i dwie sfatygowane walizki. Erdös stosował w życiu stare greckie
powiedzenie: „Człowiek mądry nie ma nic, czego nie mógłby unieść w rękach".
Przemierzał świat jako wędrowny matematyk i
nigdzie nie zatrzymywał się dłużej niż miesiąc. Był jak pszczoła przelatująca z
kwiatka na kwiatek. I podobnie jak pszczoła, która przenosi pyłek i zapładnia
krzyżowo rośliny, tak on zbierał od różnych matematyków nowe problemy i ich
rozwiązania, stosując coś w rodzaju „matematycznego krzyżowego zapłodnienia".
Wzajemne relacje między nimi były proste. Koledzy matematycy troszczyli się o
jego potrzeby fizyczne, a on obdarowywał ich w zamian owocami swojego umysłu.
Wizyty Erdösa
Ceną, jaką gospodarz musiał zapłacić za wizytę
Paula Erdösa w swoim domu, było zorganizowanie „pobytu wujka Paula". To zaś
oznaczało zaspokajanie bieżących potrzeb gościa. Poza tym trzeba było dać mu
trochę pieniędzy, zorganizować transport do następnego miejsca przeznaczenia czy
udać się do lekarza, żeby zdobyć następną porcję tabletek amfetaminy.
Substancje stymulujące, takie jak kokaina i amfetamina, zwiększają zdolność do
wysiłku. Jednocześnie jednak niszczą zdolność oceny, co jest dobre, a co jest
bezwartościowe, Można więc szybciej pracować, ale efekty tej pracy bywają
nieudane. Erdös należał do niezwykle rzadkich wyjątków, u których środki
pobudzające dawały pozytywny efekt. Ostrzegał jednak przed nimi innych
matematyków, gdyż uważał siebie za przypadek szczególny. Pierwszy raz sięgnął po
amfetaminę, gdy w 1971 roku umarła mu matka. Zaczął ją brać jako środek
antydepresyjny, zalecony przez lekarza. Potem zażywał jej w małych dziennych
dawkach przez cały czas. Jego kolega Ronald Graham martwił się, że Erdös jest
uzależniony. Wiedziony troską Graham ofiarował Erdösowi 500 dolarów, jeśli ten
na miesiąc odstawi „spidy". Erdös uważał, że małe dawki amfetaminy działają
dokładnie tak samo, jak wielka ilość kawy. Przyjął wyzwanie, ale ceną za to była
utrata kreatywności. Jak sam mówił: „Wcześniej, kiedy patrzyłem na kawałek
pustej kartki, mój umysł był pełen pomysłów. A teraz, widzę tylko pustą kartkę
papieru". Oskarżał nawet Grahama o „powstrzymanie postępów matematyki na
cały miesiąc". Erdös nie brał przez miesiąc środków pobudzających, lecz
kiedy zainkasował 500 dolarów, ponownie zaczął przyjmować amfetaminę w małych,
dziennych dawkach.
Erdös był człowiekiem zupełnie nieprzystosowanym
społecznie, o czym świadczy choćby takie zdarzenie. Pewnego razu jeden z
gospodarzy Erdösa zostawił otwarte okno, żeby ten mógł wspiąć się do pokoju,
kiedy przybędzie późno w nocy. Przed świtem rozpętała się silna burza i deszcz
zaczął zalewać parter budynku. Erdös nie zamknął okna, tylko obudził gospodarza
i powiedział: „Tam strasznie leje się przez okno. Może zrób coś z tym".
Paul miał zawsze niezachwianą pewność, że
wszystko zostanie zrobione we właściwym czasie. Na przykład, w 1984 roku
wyjechał z Ameryki do Japonii i nie wziął ze sobą żadnych czeków ani kart
kredytowych, miał przy sobie tylko 50 dolarów w gotówce. Ale wcale się tym nie
przejmował, gdyż wiedział, że jak zawsze, zatroszczą się o niego matematycy z 25
krajów, leżących na czterech kontynentach. „Nie było się czym martwić.
Wszędzie po drodze miałem przyjaciół". I nie mylił się. Dla matematyków był
bowiem Żyjącym Skarbem Narodowym.
Pojawiał się nagle u drzwi któregoś ze swoich
kolegów, w jednym z 25 krajów i ogłaszał gotowość do zajmowania się matematyką
mówiąc: „Mój mózg jest otwarty". Następnie gościł nie dłużej niż miesiąc,
aż do wyczerpania sił gospodarza. Zasilał swój mózg kawą, tabletkami kofeinowymi
i benzedryną. Obaj uczeni pracowali do wczesnych godzin porannych, po czym
wykończony gospodarz padał na łóżko.
Kilka godzin później budziło go pytanie:
„Istniejesz"?, co w wydaniu Erdösa znaczyło, czy już nie śpi. Następnie, nie
czekając na odpowiedź, Erdös przechodził do rzeczy: „Niech n będzie liczbą
całkowitą a k zbiorem takim, że..." Kiedyś na przykład wpadł na przyjęcie
bożonarodzeniowe i złapawszy swojego gospodarza za guzik zaczął: „Wesołych
świąt. Niech f od n będzie funkcją taką, że...".
Mimo to matematycy uwielbiali te wizyty, gdyż
oznaczały czas radosnych uniesień, kiedy to tańczyli z Erdösem po Matematycznej
Krainie. Żeglarze mają „żonę w każdym porcie", natomiast mottem Erdösa było:
„Inny dach, inny dowód".
Erdös nie zgadzał się zwolnić tempa, mawiał przy
tym: „W grobie będzie mnóstwo czasu na odpoczynek".
Paul
Erdös
Paul Erdös bardzo się różnił od innych
matematyków
Praktycznie, każdy matematyk spędza większość
życia zajmując się jedną dziedziną, a często nawet jednym problemem. Na przykład
Andrew Wiles spędził ładnych kilka lat, próbując dowieść Wielkiego Twierdzenia
Fermata. Konsultował się przy tym zaledwie z kilkoma kolegami. Za to Erdös
uwielbiał pracować z innymi matematykami i zajmował się jednocześnie
zagadnieniami z wielu różnych dziedzin.
Był jednym z najpłodniejszych matematyków w
historii. Typowy znakomity matematyk publikuje w ciągu życia do 100 artykułów.
Każdy artykuł zawiera nowe i oryginalne koncepcje, które nigdy przedtem nie były
publikowane. Erdös zaś ogłosił niesamowitą liczbę 1500 prac - średnio jedną na
15 dni.
Erdös zajmował się rozmaitymi dziedzinami
matematyki. Dokonał np. pionierskich odkryć w teorii liczb i kombinatoryce, na
której opiera się cała nasza wiedza z zakresu komputerów. Wraz z Markiem Kacem i
Aurel Winter zapoczątkował dziedzinę zwaną probabilistyczną teorią liczb, a
pracując z Paulem Turanem, przyczynił się bardzo do rozwoju teorii aproksymacji.
W 1949 roku Erdös zaskoczył kolegów matematyków,
kiedy, pracując z Atle Selbergiem, podał elementarny dowód twierdzenia o
liczbach pierwszych. Poprzedni dowód był poprawny, lecz „raczej nieporządny", bo
wykorzystywał pierwiastki kwadratowe z liczb ujemnych. Dowód Erdösa i Selberga
był znacznie lepszy.
Obaj uczeni umówili się, że opublikują dowód w
tym samym piśmie i w tym samym czasie. Jednakże Selberg złamał umowę i pierwszy
ogłosił wyniki, zbierając laury. Większość ludzi była tym oburzona, ale Erdös
zupełnie się nie przejął i dalej zajmował się pracą.
Jest w nauce stare powiedzenie: „To nie
odpowiedź daje Nagrodę Nobla, ale pytanie". Jedną z najwspanialszych cech
Erdösa była umiejętność stawiania pytań, mogących sprowokować interesujące
odpowiedzi. Wiedział też, do którego z matematyków należy kierować dane pytania.
Paul
Erdös
Erdös posługiwał się własną odmianą
angielskiego
Matematycy mają własny, dziwaczny język.
Twierdzenie może być „głębokie", argument przeciwko niemu „uderzający", a dowód
twierdzenia może być „piękny", „elegancki", „czysty" lub „wyjątkowo piękny".
Erdös na kobiety mówił „boss", a na mężczyzn:
„niewolnik". Dzieci zaś były dla niego „epsilonami", gdyż w matematyce litera
epsilon oznacza coś bardzo małego. „Sam" to były Stany Zjednoczone, a „Joe" (od
imienia Józefa Stalina) - Związek Radziecki. Tak więc w jego języku Show-Sama-
i-Joego były to wiadomości międzynarodowe. Alkohol nosił miano „trucizny", a
wszystko, co nie było mową, stanowiło „hałas". Tak więc „trucizna, bossy i
hałas" to odpowiednik frazy „wino, kobiety i śpiew".
Jeśli matematyk przestawał zajmować się
matematyką, Erdös mówił, że „zmarł". A kiedy ktoś naprawdę umarł, używał słowa
„wyjechał".
Erdös uważał, że Bóg, ma wielką księgę
zawierającą wszystkie najdoskonalsze i najelegantsze możliwe dowody i trzyma
swoją księgę w ukryciu, nie udostępniając jej ludziom. Zadaniem matematyków jest
wydostanie tych dowodów „wprost z księgi".
Erdös współpracował z większą liczbą matematyków
niż jakikolwiek inny matematyk w historii. Na przykład, owocem jego współpracy z
Canfieldem i Pomerance"em jest aproksymacja Erdisa, Canfielda i Pomerance’a.
Aproksymację tę można wykorzystać do odkodowania zaszyfrowanych liczb, takich
jak ogromne transakcje międzybankowe lub po prostu numer karty kredytowej, kiedy
chcemy kupić książkę przez Internet.
Liczba Erdösa
Matematycy lubią wykazywać, jak blisko byli od
napisania pracy z Erdösem - i chętnie podają swoją tzw. liczbę Erdösa.
Na przykład, w internetowej gazetce „RISKS
20-24" matematyk Martin Ward umieścił swój artykuł pt.: Regular Break-ins at the
Pentagon? Pisze on: „W każdym tygodniu notuje się setki prób włamań, z czego
99,95% to próby nie udane. Powiedzmy, że takich prób jest w tygodniu 200. To
znaczy, że w ciągu roku ma miejsce pięć „udanych" prób włamania się do systemów
Pentagonu. Okazuje się, że czasem 99,95% to wielkość niewystarczająca".
Podpisał swój artykuł: Martin Ward, liczba Erdösa 4.
Sam Erdös ma liczbę Erdösa równą zero. Około 500
matematyków ma liczbę Erdösa „jeden" - to znaczy, że napisali pracę wspólnie z
Erdösem. Około 5600 matematyków ma liczbę Erdösa „dwa". Pisali oni pracę
wspólnie z kimś, kto pisał pracę wspólnie z Erdösem.
Około 63 laureatów Nagrody Nobla ma liczbę
Erdösa poniżej dziewięciu, a wszyscy laureaci prestiżowego medalu Fieldsa za
osiągnięcia w matematyce mają liczbę Erdösa poniżej sześciu. Ronald Graham ma
liczbę Erdösa „jeden", a Albert Einstein „dwa".
Słynny gracz w baseball, Henry L. „Hank" Aaron,
ma liczbę Erdösa „dwa". Razem bowiem z Carlem Pomerance’m podpisywali tę samą
piłkę, kiedy wspólnie zostali uhonorowani stopniem naukowym na Emory University
w 1995 roku. Pomerance zaś napisał wiele prac wspólnie z Erdösem. Dzięki temu „Hank"
Aaron zyskał swoją liczbę Erdösa „dwa".
Sam Erdös żartował na temat ułamkowych liczb
Erdösa. Jeśli jakiś matematyk napisał wspólnie z nim n prac, to jego liczba
Erdösa wynosi 1/n. Inaczej mówiąc, jeśli ktoś napisał 12 prac z Erdösem, to jego
liczba Erdösa wyniesie 1/12.
Według stanu na dzień 28 lutego 2007 roku grono
osób mających liczbę Erdösa równą 1 liczy 511 osób, a 8162 osób ma liczbę Erdösa
równą 2 (oczywiście obecnie jest to najmniejsza możliwa do uzyskania wartość tej
liczby). Należy mieć świadomość, że powyższe dane, zwłaszcza odnoszące się do
wartości 2 lub wyższych, ciągle się zmieniają.
Interesującym jest fakt, że wielu naukowców
żyjących i publikujących obecnie (ale również przed Erdösem) ma skończone
(i stosunkowo niskie) liczby Erdösa. Uczeni ci reprezentują oprócz matematyki
wiele innych dyscyplin, jak informatyka, astronomia, fizyka, chemia, biologia,
genetyka, medycyna, ekonomia, lingwistyka, psychologia, filozofia i wiele
innych:
John von Neumann - Liczba Erdösa
3 (matematyka)
Albert Einstein - Liczba Erdösa
2 (fizyka)
Enrico Fermi - Liczba Erdösa 3
(fizyka)
Richard Dedekind - Liczba Erdösa
7
(matematyka)
Wacław Sierpiński - Liczba Erdösa
2(matematyka)
Niels Bohr - Liczba Erdösa 2(fizyka)
Andrew Wiles - Liczba Erdösa 3(matematyka)
George Gamow - Liczba Erdösa 5(fizyka)
J.Robert Oppenheimer - Liczba Erdösa 4(fizyka)
Edward Teller - Liczba Erdösa 4(fizyka)
Stephen Hawking - Liczba Erdösa 7(kosmologia)
Roger Penrose - Liczba Erdösa 8(kosmologia)
Francis H. C. Crick - Liczba Erdösa 7(biofizyka)
James Watson - Liczba Erdösa 8(genetyka)
Karl Popper - Liczba Erdösa
5(filozofia)
Jean Piaget - Liczba Erdösa
3(psychologia)
Noam Chomsky - Liczba Erdösa 4(lingwistyka)
Najwcześniejsze powiązania z Erdösem datują się
na drugą połowę XIX wieku. Niemiecki algebraik Georg Frobenius (1849–1917) ma
liczbę Erdösa równą 3, gdyż napisał pracę z Issai Schurem (1875–1941), który
z kolei napisał pracę ze współautorem Erdösa, Gaborem Szegö.
Obecnie prowadzone są prace nad wyznaczeniem
liczby Erdösa możliwie najszerszego kręgu naukowców. Projekt ten ma swoją stronę
internetową: The Erdös
Number Project, na której znajdują
się między innymi dane o osobach, których liczba Erdösa wynosi 1 lub 2
oraz łącza do kilku artykułów poświęconych tej liczbie.
Paul
Erdös - Oberwolfach 1993r.
Zawsze poszukiwał i wspomagał utalentowanych
młodych ludzi zainteresowanych matematyką
Erdös był człowiekiem niezwykle hojnym. Kiedy w
1984 roku otrzymał 50 tys. dolarów nagrody Wolfa, zatrzymał dla siebie tylko 750
dolarów, a resztę rozdał, głównie młodym ludziom, by ich zachęcić do matematyki.
Erdös zapalał iskrę zainteresowania wśród swoich
studentów, wypowiadając magiczne słowa: „Chciałbym przedstawić jeden z moich
ulubionych problemów". To znaczyło, że ma problem, którego sam nie
rozwiązał, ale uważa, że mógłby to zrobić ktoś słuchający jego wykładu - za
pieniądze. Zapoczątkował ten zwyczaj w 1954 roku. Nagroda pieniężna mogła
wynosić od 10 dolarów (za łatwy, ale ciekawy i podchwytliwy problem) do 10 tys.
dolarów (za problem uważany przezeń za „beznadziejny", którego rozwiązanie mogło
zająć dziesięciolecia lub nawet stulecia).
Do roku 1984 zaoferował nagrody na łączną sumę
30 tys. dolarów, z czego przyszło mu zapłacić 5 tys. dolarów. Jednakże jego
hojność wyrażała się nie tylko w dzieleniu posiadanymi pieniędzmi. Równe hojnie
służył swoim umysłem, z czego skorzystało kilka pokoleń młodych matematyków.
Zawsze poszukiwał i wspomagał utalentowanych
młodych ludzi zainteresowanych matematyką. Dawał im do rozwiązania problemy, z
którymi mogli sobie poradzić i obserwował ich postępy, traktując ich przy tym
jak równych sobie.
W 1984 roku Willy Moser, profesor matematyki na
Uniwersytecie McGilla w Montrealu powiedział: „Obecnie jest pewnie ze 100
matematyków, którzy rozwinęli się dzięki problemom, jakie Erdös im zasugerował i
pomógł rozwiązać".
Matka Erdösa mawiała:
„Paul, nawet człowiek
tak zajęty jak ty, nie może być w dwóch miejscach naraz". Paul Erdös zmarł w
Warszawie 26 września 1996 roku, po dwóch atakach serca, lub, jak mawiał w swoim
specjalnym języku, „wyjechał" w nieskończenie długą podróż, w której
niepotrzebny jest paszport.
Przypuszczalnie przebywa teraz razem z
wszystkimi wielkimi matematykami przeszłości i przyszłości i może być w wielu
miejscach naraz w tym samym czasie, „rozgryzając" matematyczne problemy i
rozwiązując jakieś naprawdę kosmiczne równania.
Paul
Erdös ze swoją matką
Grób Paula Erdösa w
Budapeszcie
Epitafium na grobie Erdősa: Végre nem butulok tovább – W końcu nie staję się
już coraz głupszy.
Jeszcze za życia Erdősa powstał o nim film dokumentalny pt.
„N Is a Number: A
Portrait of Paul Erdős"
Na zakończenie kilka ciekawych twierdzeń Erdösa:
Twierdzenie Erdösa-Mordella"
Dla dowolnego punktu O leżącego wewnątrz trójkąta ABC zachodzi nierówność:
x + y+ z
≥ 2(a + b +c)
gdzie x, y, z są
odległościami
punktu O od wierzchołków trójkąta, natomiast a, b, csą odległościami punktu O od prostych zawierających boki
trójkąta
Twierdzenie(Erdös-Szekeres, 1935)
Każdy ciąg
rzeczywisty o ab + 1 elementach zawiera (a+1) -
elementowy podciąg rosnący lub (b+1) - elementowy podciąg
malejący.
Twierdzenie
(Erdös-Szekeres, 1935)
Dla każdej
liczby naturalnej k istnieje taka liczba naturalna N
że wśród dowolnych N punktów na płaszczyźnie, z których żadne trzy nie leżą na
jednej prostej, zawsze znajdziemy k punktów, które są
wierzchołkami wypukłego k-kąta.
Prosty dowód
tezy Czebyszewa
Dla każdego n ≥ 2 między n a 2n znajduje się liczba
pierwsza. Zostało to wcześniej udowodnione przez Bertrand’a, ale dowód był
bardzo trudny i „mniej elegancki” niż Erdösa.
Uogólnienie
tego twierdzenia
Dla n ≥ 6
zawsze istnieją dwie takie liczby, co najmniej jedna postaci 4k+1,
oraz co najmniej jedna postaci 4k+3.
Twierdzenie(Erdös-Gallai, 1935)
Podział liczby
2k na n części d1 ≥ d2 ≥ ... ≥ dn
jest podziałem graficznym wtedy i tylko wtedy, gdy dla każdej liczby całkowitej
k z przedziału od 1 do n-1 jest
spełniona nierówność:
Twierdzenie(Erdös-Chvátal, 1972)
G
jest grafem o p wierzchołkach, p ≥ 3 i K(G) ≥ Β₀(G).
Wówczas G jest grafem Hamiltona. (K(G) – spójność
wierzchołkowa grafu G; Β₀(G) - największa liczność
zbioru niezależnych wierzchołków w G).
Twierdzenie
(Erdös, 1959)
Dla każdej
liczby całkowitej dodatniej k istnieje graf o liczbie
chromatycznej co najmniej k i bez cykli krótszych niż k.
Bibliografia:
Martha Claudio, Close Callas,
„Science News" vol. 154, 1998