Lemat o uściskach dłoni
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Dany jest graf prosty G o n wierzchołkach (
) i m krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność:
.
Powyższą własność nietrudno jest zrozumieć intuicyjnie: każda krawędź łączy dwa wierzchołki, a zatem dodając do siebie stopnie sąsiadujących wierzchołków (czyli liczby krawędzi wychodzących z nich), liczymy każdą z krawędzi dwukrotnie, co potwierdza prawdziwość powyższej własności.
