Dễ thấy đồ thị Hình 33 có chu trình Hamilton.

+) Sử dụng thuật toán láng giềng gần nhất đối với đỉnh xuất phát A, ta có:

Từ A, đỉnh gần nhất là B, AB = 20 nghìn đồng;

Từ B, đỉnh chưa đến gần nhất là C, BC = 30 nghìn đồng;

Từ C, đỉnh chưa đến gần nhất là D, CD = 12 nghìn đồng;

Đến đây không còn đỉnh chưa đến, vì vậy quay về A, DA = 35 nghìn đồng.  

Tổng chi phí di chuyển theo chu trình ABCDA là: 20 + 30 + 12 + 35 = 97 (nghìn đồng).

Tương tự bắt đầu với những đỉnh khác, ta có bảng sau:

Vậy có ba chu trình ABCDA, BADCB, DCBAD thỏa mãn đề bài và chi phí thấp nhất là 97 nghìn đồng.