Đề bài

Mỗi đồ thị trong Hình 23 có chu trình Euler không? Nếu có hãy chỉ ra một chu trình như vậy.

Lời giải chi tiết

⦁ Đồ thị G:

 

Ta có d(A) = d(B) = d(C) = d(D) = 4.Suy ra đồ thị G có tất cả các đỉnh đều có bậc chẵn.Vậy đồ thị G có chu trình Euler.Chẳng hạn, ta có chu trình Euler: AabACDBcdBA.⦁ Đồ thị H:Ta có d(A) = d(B) = d(E) = 4; d(C) = d(D) = 3.Suy ra đồ thị H có hai đỉnh C, D có bậc lẻ.Vậy đồ thị H không có chu trình Euler.