Định lí 2 (Còn được gọi là bổ đề bắt tay.)
Cho đồ thị $G = (V, E)$. Khi đó
$$2|E| =\sum\limits_{v \in {\kern 1pt} V} {\deg (v)} $$
Chứng minh Chứng minh
Mỗi cạnh $e = (u,v)$ được tính một lần trong $deg(u)$ và một lần trong $deg(v)$. Vậy tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn.
Áp dụng định lí này bạn đọc có thể giải quyết bài toán sau.
Không yêu cầu chứng minh bài toán ở topic này.
Trong một buổi họp có $n$ người tham gia và có một số cái bắt tay (mỗi cái bắt tay tạo thành từ hai người, hai người đã bắt rồi thì không bắt tay lại). Chứng minh rằng nếu số người tham gia bắt tay là một số lẻ thì số cái bắt tay được tạo ra là một số chẵn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]