Lemat o uściskach dłoni

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

${\displaystyle \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^[1].