Luyện tập 1: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.
Bài Làm:
Đồ thị 2.19a liên thông, chỉ có hai đỉnh A và B có bậc lẻ (bậc bằng 3), các đỉnh còn lại đều bậc chẵn. Do đó đồ thị có đường đi Euler. Đường đi Euler trong đồ thị: ACBEADB.
Đồ thị 2.19b liên thông nhưng tất cả các đỉnh đều có bậc lẻ nên đồ thị không có đường đi Euler.