1. Nội dung câu hỏi
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ùng bậc.
2. Phương pháp giải
Đọc kĩ yêu cầu, gợi nhớ kiến thức để thực hiện.
3. Lời giải chi tiết
Giả sử G là một đơn đồ thị có n đỉnh (n ≥ 2).
Vì G là đơn đồ thị nên mỗi đỉnh của G không có khuyên và chỉ có thể nối với các đỉnh khác không quá một cạnh, nghĩa là mỗi đỉnh của G có bậc tối đa là (n – 1) (*).
Giả sử bậc của các đỉnh của G đều khác nhau. Khi đó bậc của n đỉnh của G lần lượt là 0, 1, ..., (n – 1), nghĩa là G phải có đỉnh bậc 0.
Do G có đỉnh bậc 0 nên các đỉnh khác của G có bậc tối đa là (n – 2) (mâu thuẫn (*)).
Vậy có ít nhất 2 đỉnh của G có cùng bậc.
Chủ đề 3: Đại cương về hóa học hữu cơ
Tải 20 đề kiểm tra 15 phút - Chương III - Hóa học 11
Unit 4: Planet Earth
Chủ đề 2. Khám phá bản thân
Unit 8: Conservation
SGK Toán Lớp 11
SGK Toán Nâng cao Lớp 11
SBT Toán Lớp 11
SBT Toán Nâng cao Lớp 11
SGK Toán 11 - Kết nối tri thức với cuộc sống
SGK Toán 11 - Cánh Diều
SGK Toán 11 - Chân trời sáng tạo
Chuyên đề học tập Toán 11 - Cánh Diều
Chuyên đề học tập Toán 11 - Chân trời sáng tạo
SBT Toán 11 - Kết nối tri thức với cuộc sống
SBT Toán 11 - Cánh Diều
SBT Toán 11 - Chân trời sáng tạo
Tổng hợp Lí thuyết Toán 11
Bài giảng ôn luyện kiến thức môn Toán lớp 11