Một người đưa thư xuất phát từ bưu điện ở vị trí A, các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu?

(AI giải đề cho tôi)
Đây là bài toán người đưa thư (Chinese Postman) trên đồ thị với các cạnh: AB = 8, BC = 5, CD = 2, BD = 4, DE = 9, BE = 10, và hai con đường song song A–E dài 7 và 6. Tổng độ dài tất cả các con đường: 8 + 5 + 2 + 4 + 9 + 10 + 7 + 6 = 51. Xét bậc các đỉnh: bậc A = 3 (lẻ), bậc B = 4, bậc C = 2, bậc D = 3 (lẻ), bậc E = 4. Vậy chỉ có hai đỉnh bậc lẻ là A và D, nên cần lặp lại một đường đi ngắn nhất từ A đến D. Các phương án: A–B–D = 8 + 4 = 12; A–E–D = 6 + 9 = 15 hoặc 7 + 9 = 16; A–E–B–D = 7 + 10 + 4 = 21; A–B–E–D = 8 + 10 + 9 = 27. Đường ngắn nhất là A–B–D = 12. Khi đó tổng quãng đường ngắn nhất (đi mỗi cạnh ít nhất một lần, lặp lại đường A–B–D, chu trình Euler tồn tại sau khi nhân đôi) là 51 + 12 = 63 (đơn vị độ dài).