Số màu trong đồ thị hình bánh xe W_n (với n lẻ) là:

Thuật toán Dijkstra là một thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn đến tất cả các đỉnh còn lại trong một đồ thị có trọng số không âm.

- Phương án A: "Đồ thị vô hướng hoặc có hướng có trọng số không âm." Đây là đáp án chính xác vì thuật toán Dijkstra có thể áp dụng cho cả đồ thị vô hướng và đồ thị có hướng, miễn là trọng số của các cạnh không âm.

- Phương án B: "Đồ thị liên thông có trọng số không âm" Mặc dù thuật toán Dijkstra thường được áp dụng cho đồ thị liên thông, nhưng tính liên thông không phải là một yêu cầu bắt buộc. Thuật toán vẫn hoạt động đúng nếu đồ thị không liên thông, nó chỉ tìm đường đi ngắn nhất đến các đỉnh có thể đạt được từ đỉnh nguồn.

- Phương án C: "Đồ thị có hướng có trọng số không âm." Thuật toán Dijkstra có thể dùng cho đồ thị vô hướng và có hướng, nên đáp án này chưa bao quát hết.

- Phương án D: "Đồ thị vô hướng hoặc có hướng không có chu trình âm" Điều kiện "không có chu trình âm" liên quan đến thuật toán Bellman-Ford chứ không phải Dijkstra. Dijkstra yêu cầu trọng số không âm, chứ không cấm chu trình âm.

Do đó, đáp án chính xác nhất là A.

Đơn đồ thị (simple graph) là một loại đồ thị vô hướng không chứa khuyên (loop) và không chứa cạnh bội (multiple edges). Khuyên là cạnh nối một đỉnh với chính nó. Cạnh bội là hai hay nhiều cạnh nối cùng một cặp đỉnh. Do đó, đáp án đúng là A.

Trong đồ thị vô hướng, bậc của một đỉnh là số cạnh liên thuộc với đỉnh đó. Đỉnh v có bậc bằng 1 nghĩa là có đúng một cạnh nối với nó.

* Đáp án A đúng: "Có một cạnh xuất phát từ v" chính xác mô tả định nghĩa của một đỉnh có bậc 1 trong đồ thị vô hướng.
* Đáp án B sai: "Có hơn một cạnh xuất phát từ v" nghĩa là đỉnh v có bậc lớn hơn 1.
* Đáp án C sai: "Có đúng một cạnh đi vào và có hơn một đỉnh đi ra khỏi đỉnh này" không phù hợp với định nghĩa bậc của đỉnh trong đồ thị vô hướng. Hơn nữa, cách diễn đạt "đi vào" và "đi ra" thường được sử dụng cho đồ thị có hướng.
* Đáp án D sai: "Tồn tại khuyên ở đỉnh đó" có nghĩa là có một cạnh nối đỉnh đó với chính nó. Mỗi khuyên sẽ làm tăng bậc của đỉnh lên 2, nên đỉnh đó sẽ có bậc ít nhất là 2.

Chu trình Hamilton là một chu trình trong đồ thị mà đi qua mỗi đỉnh của đồ thị đúng một lần, trừ đỉnh bắt đầu (và kết thúc) của chu trình. Do đó, đáp án đúng là B.