5) Một đồ thị n đỉnh (n ≥ 4) mà cứ bốn đỉnh tuỳ ý thì có ít nhất một đỉnh kề với
ba đỉnh còn lại, thì có số đỉnh bậc n-1 không ít hơn n-3.
- Nếu đồ thị G đầy đủ hoặc chỉ có duy nhất hai đỉnh không kề nhau thì trong
G có ít nhất n-2 đỉnh bậc n-1.
- Nếu đồ thị G có ba đỉnh không kề nhau là a, b, c. Các đỉnh khác phải kề
nhau và kề với 3 đỉnh trên. Do vậy số đỉnh có bậc n-1 là n-3.
Bạn đang xem 5) - BAI_02