Giải Bài 2.22 trang 50 Chuyên đề Toán 11
Đề bài
Chứng minh rằng nếu là một đơn đồ thị có ít nhất hai đỉnh thì có ít nhất hai đỉnh có cùng bậc.
Lời giải
Chứng minh
Gọi là đơn đồ thị có đỉnh ().
Bước 1. Xác định tập giá trị có thể của bậc.
Vì là đơn đồ thị có đỉnh nên mỗi đỉnh chỉ có thể kề với tối đa đỉnh còn lại. Do đó bậc của mỗi đỉnh là một số nguyên thuộc tập
Bước 2. Chỉ ra bậc và bậc không thể cùng xuất hiện.
Giả sử trong có đỉnh với , tức là không kề với đỉnh nào. Khi đó mọi đỉnh khác đều không kề với , nên không đỉnh nào kề được với đủ cả đỉnh còn lại, nghĩa là không tồn tại đỉnh có bậc .
Vậy trong không thể đồng thời có đỉnh bậc và đỉnh bậc . Suy ra bậc của đỉnh chỉ nhận giá trị trong một trong hai tập:
Mỗi tập đều chỉ có phần tử.
Bước 3. Áp dụng nguyên lý Dirichlet.
Ta có đỉnh nhưng bậc của chúng chỉ nhận tối đa giá trị phân biệt. Theo nguyên lý Dirichlet, phải tồn tại ít nhất hai đỉnh có cùng bậc.
Vậy mọi đơn đồ thị có ít nhất hai đỉnh đều có ít nhất hai đỉnh cùng bậc (đpcm).
Đáp số
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.