Chuyên đề học tập Toán 11

Giải Bài 2.22 trang 50 Chuyên đề Toán 11

Bài tập cuối chuyên đề 2   Đã kiểm chéo

Đề bài

Chứng minh rằng nếu GG là một đơn đồ thị có ít nhất hai đỉnh thì GG có ít nhất hai đỉnh có cùng bậc.

Lời giải

Chứng minh

Gọi GG là đơn đồ thị có nn đỉnh (n≥2n \geq 2).

Bước 1. Xác định tập giá trị có thể của bậc.

Vì GG là đơn đồ thị có nn đỉnh nên mỗi đỉnh chỉ có thể kề với tối đa n−1n-1 đỉnh còn lại. Do đó bậc của mỗi đỉnh là một số nguyên thuộc tập
{0, 1, 2, …, n−1}.\{0,\, 1,\, 2,\, \ldots,\, n-1\}.

Bước 2. Chỉ ra bậc 00 và bậc n−1n-1 không thể cùng xuất hiện.

Giả sử trong GG có đỉnh uu với deg⁡(u)=0\deg(u) = 0, tức là uu không kề với đỉnh nào. Khi đó mọi đỉnh khác đều không kề với uu, nên không đỉnh nào kề được với đủ cả n−1n-1 đỉnh còn lại, nghĩa là không tồn tại đỉnh có bậc n−1n-1.

Vậy trong GG không thể đồng thời có đỉnh bậc 00 và đỉnh bậc n−1n-1. Suy ra bậc của nn đỉnh chỉ nhận giá trị trong một trong hai tập:
{0, 1, …, n−2}hoặc{1, 2, …, n−1}.\{0,\, 1,\, \ldots,\, n-2\} \quad \text{hoặc} \quad \{1,\, 2,\, \ldots,\, n-1\}.

Mỗi tập đều chỉ có n−1n-1 phần tử.

Bước 3. Áp dụng nguyên lý Dirichlet.

Ta có nn đỉnh nhưng bậc của chúng chỉ nhận tối đa n−1n-1 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ị GG có ít nhất hai đỉnh đều có ít nhất hai đỉnh cùng bậc (đpcm).

Đáp số

đpcm

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.