Lemat o uściskach dłoni

Dany jest graf prosty $G$ o $n$ wierzchołkach $(v_{1},v_{2},\dots ,v_{n})$ i $m$ krawędziach. Na mocy lematu o uściskach dłoni spełniona jest następująca własność:

$\sum _{i=1}^{n}\deg(v_{i})=2m.$

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.