Giải chuyên đề học tập Toán lớp 11 Kết nối tri thức Bài tập cuối chuyên đề 2 Chuyên đề học tập Toán 11 kết ..

Giải bài 2.22 trang 50 Chuyên đề học tập Toán 11 Kết nối tri thức


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.

Đề bà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.

Phương pháp giải - Xem chi tiết

Một đồ thị không có khuyên, trong đó hai đỉnh được nối bằng nhiều nhất một cạnh (không có hai cạnh nào cùng nối một cặp đỉnh) gọi là một đơn đồ thị.

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.


Bình chọn:
4.9 trên 7 phiếu
Bài tiếp theo

>> Xem thêm

Luyện Bài Tập Trắc nghiệm Toán 11 - Kết nối tri thức - Xem ngay

Báo lỗi - Góp ý

Tham Gia Group Dành Cho 2K8 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

Các bài khác cùng chuyên mục


App Loigiaihay trên google play store App Loigiaihay trên apple store

Copyright © 2021 loigiaihay.com

DMCA.com Protection Status
App Loigiaihay trên apple store App Loigiaihay trên google play store