Số đỉnh bậc lẻ trong đồ thị G vô hướng:
Trả lời:
Đáp án đúng: C
Định lý: Trong một đồ thị vô hướng, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh của đồ thị.
Gọi V là tập hợp các đỉnh của đồ thị G. Ta có:
∑deg(v) = 2|E|, với v ∈ V, trong đó |E| là số cạnh của đồ thị.
Tổng bậc của các đỉnh luôn là một số chẵn.
Giả sử V_l là tập hợp các đỉnh bậc lẻ và V_c là tập hợp các đỉnh bậc chẵn. Ta có:
∑deg(v) = ∑deg(v_l) + ∑deg(v_c) = 2|E|, với v ∈ V, v_l ∈ V_l, v_c ∈ V_c
Vì ∑deg(v_c) là một số chẵn, nên ∑deg(v_l) cũng phải là một số chẵn để tổng của chúng là một số chẵn.
Để ∑deg(v_l) là một số chẵn, số lượng các đỉnh bậc lẻ (|V_l|) phải là một số chẵn, vì mỗi deg(v_l) là một số lẻ.
Do đó, số đỉnh bậc lẻ trong đồ thị vô hướng G là một số chẵn.
Vậy đáp án đúng là C.





