Bài toán 28

Đáp án:

(1) Xe có thể xuất phát từ A hoặc C. Đường đi của xe có thể là: ABCDFGEFAC (xuất phát từ A và kết thúc ở C) hoặc CABCDFGEFA (xuất phát từ C và kết thúc ở A)

(2) Với mỗi đỉnh, ta tính số đường nối với nó (kề với nó). Ví dụ, với điểm A có 3 đường nối với nó (ta thường gọi là ngã ba), ký hiệu A(3); điểm G có 4 con đường nối với nó (G là ngã tư), ký hiệu G(4). Tương tự: B(2), C(3), D(2), F(4), G(4), E(4), K(4), H(4). Ta có nhận xét: nếu có đường đi đi qua tất cả các đoạn đường và mỗi đoạn đường đi qua đúng 1 lần thì bất cứ điểm nào trên đường đi (trừ điểm xuất phát và điểm kết thúc) luôn có số đường nối với nó là số chẵn (vì cứ có đường đi vào thì lại có đường đi ra). Tức là điểm trong đường đi (trừ đầu và cuối) phải là các điểm ngã hai, ngã tư, ngã sáu, v.v. (ngã chẵn), chứ không thể là ngã ba, ngã năm, v.v. (ngã lẻ). Trong số các điểm trên hình vẽ, chỉ có 2 điểm A và C có số đường nối với nó là số lẻ (đều là 3) => Điểm xuất phát của đường đi phải là A hoặc C, tức là điểm xuất phát là điểm có số đường nối với nó là số lẻ.