CĐ2 - Bài 8: Một vài khái niệm cơ bản

• Các cạnh nối với $A$: $AB, DA, AC \Rightarrow deg(A) = 3$.

• Các cạnh nối với $B$: $AB, BC \Rightarrow deg(B) = 2$.

• Các cạnh nối với $C$: $BC, CD, AC \Rightarrow deg(C) = 3$.

• Các cạnh nối với $D$: $CD, DA \Rightarrow deg(D) = 2$.

• $K_5$ có 5 đỉnh.

• Số cạnh $|E| = C_5^2 = \dfrac{5 \times 4}{2} = 10$ cạnh.

• Mỗi đỉnh nối với 4 đỉnh còn lại $\Rightarrow deg(v) = 4$ với mọi đỉnh $v$.

Mỗi đỉnh có bậc 3 $\Rightarrow$ Tổng bậc $= 4 \times 3 = 12$ (bằng $2 \times 6$ cạnh).

Tổng bậc $= 2 + 3 + 3 + 4 + 4 = 16$ (chẵn), số đỉnh bậc lẻ là 2 (chẵn) $\Rightarrow$ Tồn tại đồ thị như vậy.

• Tổng bậc tất cả các đỉnh $= 6 \times 3 = 18$.

• Số cạnh $|E| = \dfrac{18}{2} = 9$ cạnh.

• Tổng bậc $= 2 |E| = 2 \times 10 = 20$.

• Gọi $x$ là số đỉnh bậc 2. Tổng bậc $= 4(3) + x(2) = 12 + 2x = 20 \Rightarrow 2x = 8 \Rightarrow x = 4$.

• Tổng số đỉnh của $G$ là $4 + 4 = 8$ đỉnh.

Tổng bậc $= 9 \times 3 = 27$ (lẻ) $\Rightarrow$ Không thể xảy ra theo định lí bắt tay.

$3(4) + x(1) = 2(8) = 16 \Rightarrow 12 + x = 16 \Rightarrow x = 4 \Rightarrow$ Tổng cộng $3 + 4 = 7$ đỉnh.

• $deg(E) = 0 \Rightarrow E$ là đỉnh cô lập.

• Không có đường đi từ $E$ đến $A, B, C, D \Rightarrow$ Đồ thị $G$ **không liên thông**.

Chu trình $A \to B \to C \to D \to A$ có độ dài 4 cạnh.

Có, vì hai đỉnh bất kì luôn có cạnh nối trực tiếp.

Bằng 3 (tam giác).

• Bậc của các đỉnh: $deg(A) = 2, deg(B) = 2, deg(C) = 3, deg(D) = 2, deg(E) = 1$.

• Thành phố C có nhiều đường bay nhất (3 tuyến bay).

Không thể, vì nếu có thì tổng bậc sẽ là $7 \times 3 = 21$ (số lẻ), vi phạm định lí bắt tay.

Mô hình đồ thị đầy đủ $K_6 \Rightarrow |E| = C_6^2 = 15$ trận đấu.

Đồ thị có 20 đỉnh, bậc của mỗi đỉnh $\in \{0, 1, ..., 19\}$. Không thể đồng thời có đỉnh bậc 0 và đỉnh bậc 19. Áp dụng nguyên lí Dirichlet cho 20 đỉnh vào 19 giá trị bậc $\Rightarrow$ Tồn tại 2 đỉnh có cùng bậc.