Khi xây dựng chu trình Hamilton, nếu lấy hai cạnh liên thuộc với một đỉnh đặt vào chu trình thì:

Đồ thị bánh xe W_n được tạo ra bằng cách nối một đỉnh trung tâm vào tất cả các đỉnh của một đồ thị chu trình C_n.

Khi n lẻ, đồ thị chu trình C_n có số màu là 3. Đỉnh trung tâm kề với tất cả các đỉnh của C_n. Do đó, ta có thể tô màu cho đỉnh trung tâm bằng màu thứ hai mà không trùng với bất kỳ đỉnh nào trên C_n.

Vì vậy, số màu của đồ thị bánh xe W_n khi n lẻ là 3.

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.