Bậc của đỉnh trong đồ thị có hướng G là:

Đồ thị C_n (đồ thị chu trình) là một đồ thị có n đỉnh và n cạnh, trong đó các đỉnh được sắp xếp thành một chu trình. Mỗi đỉnh được nối với hai đỉnh lân cận. Vì vậy, số đỉnh là n và số cạnh cũng là n.

Đường đi Hamilton là đường đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Đây là định nghĩa cơ bản của đường đi Hamilton.

Bài toán xây dựng cây khung nhỏ nhất (Minimum Spanning Tree - MST) áp dụng cho đồ thị vô hướng, có trọng số và các trọng số này thường là dương. Các thuật toán như Kruskal và Prim đều dựa trên việc chọn cạnh có trọng số nhỏ nhất để thêm vào cây khung, do đó trọng số âm có thể gây ra các vấn đề và kết quả sai lệch. Đồ thị có hướng không phù hợp vì cây khung không quan tâm đến hướng của cạnh.

Lát cắt (X, Y) trong một mạng G là một sự phân hoạch tập đỉnh V thành hai tập con X và Y sao cho X ∪ Y = V và X ∩ Y = ∅. Khi đó, lát cắt (X, Y) được định nghĩa là tập hợp tất cả các cung (vᵢ, vⱼ) mà vᵢ ∈ X và vⱼ ∈ Y hoặc vⱼ ∈ X và vᵢ ∈ Y. Điều này có nghĩa là tập hợp các cạnh nối một đỉnh từ tập X sang tập Y hoặc ngược lại, từ Y sang X. Đáp án số 2 mô tả chính xác định nghĩa này.

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh K, ta duyệt tất cả các đỉnh kề với K (A và I), sau đó duyệt tất cả các đỉnh kề với A và I (chưa được duyệt), và cứ tiếp tục như vậy cho đến khi tất cả các đỉnh đã được duyệt. Bước 1: Bắt đầu từ K. Bước 2: Duyệt các đỉnh kề với K: A, I. Bước 3: Duyệt các đỉnh kề với A: B, C, E. Bước 4: Duyệt các đỉnh kề với I: Không có đỉnh mới. Bước 5: Duyệt các đỉnh kề với B: D. Bước 6: Duyệt các đỉnh kề với C: Không có đỉnh mới. Bước 7: Duyệt các đỉnh kề với E: F, G. Bước 8: Duyệt các đỉnh kề với D: Không có đỉnh mới. Bước 9: Duyệt các đỉnh kề với F: H. Bước 10: Duyệt các đỉnh kề với G: Không có đỉnh mới. Bước 11: Duyệt các đỉnh kề với H: Không có đỉnh mới. Kết quả duyệt theo BFS(K) là: K, A, I, B, C, E, D, F, G, H. Tuy nhiên thứ tự B, C, E và D, F, G, H có thể thay đổi tùy thuộc vào thứ tự duyệt các đỉnh kề trong danh sách kề. Trong các đáp án, đáp án gần đúng nhất là K, A, B, C, D, E, F, G, H, I. Tuy nhiên, I phải đứng sau A, và thứ tự đúng phải là K, A, I, B, C, E, D, F, G, H. Vì không có đáp án nào hoàn toàn chính xác, ta chọn đáp án gần đúng nhất. Thực tế, nếu ta xét thứ tự duyệt các đỉnh kề của K là A rồi đến I thì thứ tự duyệt sẽ là K, A, I, sau đó duyệt các đỉnh kề của A (B, C, E), rồi đến lượt các đỉnh kề của I (không có). Tiếp tục duyệt các đỉnh kề của B (D), của C (không có), của E (F, G), của D (không có), của F (H), của G (không có), của H (không có). Vậy thứ tự duyệt sẽ là K, A, I, B, C, E, D, F, G, H. Vì vậy đáp án 1 là gần đúng nhất.