Đồ thị G là không liên thông nếu nó chứa:

Chu trình trong đồ thị là một đường đi, trong đó đỉnh đầu và đỉnh cuối của đường đi đó trùng nhau. Điều này có nghĩa là ta có thể bắt đầu từ một đỉnh, đi qua một số đỉnh khác và quay trở lại đỉnh ban đầu.

Do đó, đáp án đúng là B.

Một đồ thị vô hướng được gọi là cây nếu nó liên thông và không có chu trình. Điều này tương đương với việc nó liên thông và có số cạnh bằng số đỉnh trừ 1 (n-1).

A. Đúng, nếu đồ thị liên thông và có n-1 cạnh thì nó là một cây.

B. Sai, cây phải liên thông.

C. Sai, nếu đồ thị liên thông và có n cạnh thì nó chứa chu trình, do đó không phải là cây.

D. Sai, cây phải liên thông.

Để xác định xem một dãy số có thể là bậc của các đỉnh trong một đồ thị vô hướng hay không, ta sử dụng định lý sau: Một dãy số nguyên không âm d±ợc sắp xếp theo thứ tự giảm dần d₁, d₂, ..., d_n là dãy bậc của một đồ thị vô hướng khi và chỉ khi Σd_i chẵn.

A. 2 + 4 + 3 + 1 + 4 + 2 + 5 = 21 (lẻ) - không tồn tại

B. 3 + 4 + 2 + 1 + 4 + 2 + 6 = 22 (chẵn)- có thể tồn tại

C. 5 + 2 + 2 + 1 + 3 + 2 + 4 = 19 (lẻ) - không tồn tại

D. 2 + 1 + 4 + 3 + 4 + 2 + 7 = 23 (lẻ) - không tồn tại

Vậy, chỉ có B là có thể tồn tại.