2.22. Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh có cùng bậc.
Bài Làm:
Gọi số đỉnh của đồ thị là n (n $\geq $ 2)
Theo Nguyên lí chuồng bồ câu: Nếu một số lượng n vật thể được đặt vào m chuồng bồ câu, với điều kiện n > m, thì ít nhất một chuồng bồ câu sẽ có nhiều hơn 1 vật thể.
Một bậc của một đỉnh coi như một chuồng: tối đa n - 1, tối thiểu là 1.
Ví dụ: n = 10, 10 đỉnh có tối thiểu: bậc 1; tối đa: bậc 9.
Đồ thị có 10 đỉnh thì có hai đỉnh cùng bậc. (đcpcm)
