WTwierdzenie Bondy’ego-Chvátala – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski.
WTwierdzenie Brooksa – w teorii grafów twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i liczbą chromatyczną w grafie. Nazwa twierdzenia została ustanowiona na cześć angielskiego matematyka Rowlanda Leonarda Brooksa, który opublikował jego dowód w 1941 roku.
WTwierdzenie Diraca – twierdzenie pozwalające stwierdzić, czy graf jest hamiltonowski, zostało sformułowane w roku 1952. Nazwa pochodzi od Gabriela Diraca.
WGraf eulerowski, graf Eulera – rodzaj grafu rozpatrywany w teorii grafów. Graf eulerowski odznacza się tym, że da się w nim skonstruować cykl Eulera, czyli cykl, który przechodzi przez każdą jego krawędź dokładnie raz. Pierwszy raz problem poszukiwania cyklów w grafach został podniesiony przez szwajcarskiego matematyka, Leonharda Eulera w roku 1736, który chciał rozwiązać zagadnienie mostów królewieckich. Aby odszukać cykl Eulera w grafie można posłużyć się algorytmem Fleury’ego.
WTwierdzenie o kojarzeniu małżeństw – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w roku 1935. Jest ono często ilustrowane poprzez przedstawienie następującego problemu:
WTwierdzenie Kuratowskiego – twierdzenie teorii grafów sformułowane i udowodnione przez Kazimierza Kuratowskiego w 1930 roku.
WTwierdzenie o czterech barwach – dla każdego skończonego grafu planarnego istnieje funkcja taka że czyli możliwe jest przypisanie każdemu z jego wierzchołków jednej z czterech liczb 1, 2, 3 i 4 w taki sposób, aby żadne sąsiednie wierzchołki nie miały przyporządkowanej tej samej liczby. Jest to jeden z najsłynniejszych problemów matematycznych.
WTwierdzenie o kojarzeniu małżeństw – przypisywane zazwyczaj Philipowi Hallowi twierdzenie dotyczące istnienia pełnego skojarzenia grafu dwudzielnego, sformułowane w roku 1935. Jest ono często ilustrowane poprzez przedstawienie następującego problemu:
WTwierdzenie o liczbie krawędzi pozwala stwierdzić, czy graf jest hamiltonowski.
WDany jest graf prosty o wierzchołkach i krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność:
WTwierdzenie Orego – twierdzenie podające warunek wystarczający na to, aby graf miał cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øysteina Orego.
WTwierdzenie Ramseya – twierdzenie matematyczne dotyczące teorii grafów, udowodnione przez F. Ramseya.