Lemat o uściskach dłoni

Dany 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ść:

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. Wynika z tego również fakt, że w dowolnym grafie liczba wierzchołków o nieparzystych stopniach jest parzysta.

Jako pierwszy zauważył tę własność Leonhard Euler w 1736 roku[1].

Copyright